基于内存的存储的持久性

Durability in Memory-Based Stores

内存数据库系统在磁盘上维护备份以提供持久性并防止易失性数据丢失。有些数据库将数据专门存储在内存中，没有任何持久性保证，但我们不在本书的范围内讨论它们。

In-memory database systems maintain backups on disk to provide durability and prevent loss of the volatile data. Some databases store data exclusively in memory, without any durability guarantees, but we do not discuss them in the scope of this book.

在认为操作完成之前，必须将其结果写入顺序日志文件。我们在“恢复”中更详细地讨论预写日志。为了避免在启动期间或崩溃后重播完整的日志内容，内存中存储维护备份副本。备份副本被维护为排序的基于磁盘的结构，对此结构的修改通常是异步的（与客户端请求解耦）并批量应用，以减少 I/O 操作的数量。在恢复期间，可以从备份和日志中恢复数据库内容。

Before the operation can be considered complete, its results have to be written to a sequential log file. We discuss write-ahead logs in more detail in “Recovery”. To avoid replaying complete log contents during startup or after a crash, in-memory stores maintain a backup copy. The backup copy is maintained as a sorted disk-based structure, and modifications to this structure are often asynchronous (decoupled from client requests) and applied in batches to reduce the number of I/O operations. During recovery, database contents can be restored from the backup and logs.

日志记录通常应用于批量备份。处理完这批日志记录后，备份会保存特定时间点的数据库快照，直到该时间点的日志内容都可以被丢弃。这个过程称为检查点。它通过使磁盘驻留数据库保持最新的日志条目来减少恢复时间，而无需客户端阻塞直到备份更新。

Log records are usually applied to backup in batches. After the batch of log records is processed, backup holds a database snapshot for a specific point in time, and log contents up to this point can be discarded. This process is called checkpointing. It reduces recovery times by keeping the disk-resident database most up-to-date with log entries without requiring clients to block until the backup is updated.

基于磁盘的数据库使用专门的存储结构，针对磁盘访问进行了优化。在内存中，指针的跟随速度相对较快，并且随机内存访问比随机磁盘访问要快得多。基于磁盘的存储结构通常具有宽而短的树形式（请参阅“基于磁盘的存储的树”），而基于内存的实现可以从更大的数据结构池中进行选择，并执行原本不可能或困难的优化在磁盘上实现[MOLINA92]。同样，处理磁盘上的可变大小数据需要特别注意，而在内存中通常需要使用指针引用值。

Disk-based databases use specialized storage structures, optimized for disk access. In memory, pointers can be followed comparatively quickly, and random memory access is significantly faster than the random disk access. Disk-based storage structures often have a form of wide and short trees (see “Trees for Disk-Based Storage”), while memory-based implementations can choose from a larger pool of data structures and perform optimizations that would otherwise be impossible or difficult to implement on disk [MOLINA92]. Similarly, handling variable-size data on disk requires special attention, while in memory it’s often a matter of referencing the value with a pointer.

对于某些用例，可以合理地假设整个数据集适合内存。某些数据集受其现实世界表示的限制，例如学校的学生记录、公司的客户记录或在线商店中的库存。每条记录占用的空间不超过几Kb，且数量有限。

For some use cases, it is reasonable to assume that an entire dataset is going to fit in memory. Some datasets are bounded by their real-world representations, such as student records for schools, customer records for corporations, or inventory in an online store. Each record takes up not more than a few Kb, and their number is limited.

面向行的数据布局

Row-Oriented Data Layout

面向行的数据库管理系统将数据存储在记录或行中。它们的布局非常接近表格数据表示，其中每行都有相同的字段集。例如，面向行的数据库可以有效地存储用户条目、持有者姓名、出生日期和电话号码：

Row-oriented database management systems store data in records or rows. Their layout is quite close to the tabular data representation, where every row has the same set of fields. For example, a row-oriented database can efficiently store user entries, holding names, birth dates, and phone numbers:

| 身份证 | 名称 | 出生日期 | 电话号码 |
| 10 | 10 约翰 | 1981 年 8 月 1 日 | +1 111 222 333 |
| 20 | 山姆 | 1988 年 9 月 14 日 | +1 555 888 999 |
| 30| 基思| 1984 年 1 月 7 日 | +1 333 444 555 |

| ID | Name  | Birth Date  | Phone Number   |
| 10 | John  | 01 Aug 1981 | +1 111 222 333 |
| 20 | Sam   | 14 Sep 1988 | +1 555 888 999 |
| 30 | Keith | 07 Jan 1984 | +1 333 444 555 |

这种方法适用于由多个字段构成由键（在本例中为单调递增数字）唯一标识的记录（姓名、出生日期和电话号码）的情况。代表单个用户记录的所有字段通常一起读取。创建记录时（例如，当用户填写注册表时），我们也将它们写在一起。同时，每个字段都可以单独修改。

This approach works well for cases where several fields constitute the record (name, birth date, and a phone number) uniquely identified by the key (in this example, a monotonically incremented number). All fields representing a single user record are often read together. When creating records (for example, when the user fills out a registration form), we write them together as well. At the same time, each field can be modified individually.

由于面向行的存储在我们必须按行访问数据的情况下最有用，因此将整行存储在一起可以提高空间局部性² [DENNING68]。

Since row-oriented stores are most useful in scenarios when we have to access data by row, storing entire rows together improves spatial locality² [DENNING68].

由于磁盘等持久介质上的数据通常是按块访问的（换句话说，磁盘访问的最小单位是块），因此单个块将包含所有列的数据。这对于我们想要访问整个用户记录的情况非常有用，但会使访问多个用户记录的各个字段的查询（例如，仅获取电话号码的查询）更加昂贵，因为其他字段的数据将被分页也在。

Because data on a persistent medium such as a disk is typically accessed block-wise (in other words, a minimal unit of disk access is a block), a single block will contain data for all columns. This is great for cases when we’d like to access an entire user record, but makes queries accessing individual fields of multiple user records (for example, queries fetching only the phone numbers) more expensive, since data for the other fields will be paged in as well.

面向列的数据布局

Column-Oriented Data Layout

面向列的数据库管理系统垂直（即按列）划分数据，而不是将其存储在行中。这里，同一列的值连续存储在磁盘上（与前面示例中连续存储行相反）。例如，如果我们存储历史股票市场价格，则报价会存储在一起。将不同列的值存储在单独的文件或文件段中可以实现按列的高效查询，因为可以一次性读取它们，而不是消耗整行并丢弃未查询的列的数据。

Column-oriented database management systems partition data vertically (i.e., by column) instead of storing it in rows. Here, values for the same column are stored contiguously on disk (as opposed to storing rows contiguously as in the previous example). For example, if we store historical stock market prices, price quotes are stored together. Storing values for different columns in separate files or file segments allows efficient queries by column, since they can be read in one pass rather than consuming entire rows and discarding data for columns that weren’t queried.

面向列的存储非常适合计算聚合的分析工作负载，例如查找趋势、计算平均值等。处理复杂聚合可用于逻辑记录具有多个字段的情况，但其中一些字段（在本例中，价格报价）具有不同的重要性，并且经常一起使用。

Column-oriented stores are a good fit for analytical workloads that compute aggregates, such as finding trends, computing average values, etc. Processing complex aggregates can be used in cases when logical records have multiple fields, but some of them (in this case, price quotes) have different importance and are often consumed together.

从逻辑上看，代表股市价格行情的数据仍然可以用表格来表示：

From a logical perspective, the data representing stock market price quotes can still be expressed as a table:

| 身份证 | 符号| 日期 | 价格|
| 1 | 陶氏化学 | 2018 年 8 月 8 日 | 24,314.65 |
| 2 | 陶氏化学 | 2018 年 8 月 9 日 | 24,136.16 | 24,136.16
| 3 | 标准普尔 | 2018 年 8 月 8 日 | 2,414.45 | 2,414.45
| 4 | 标准普尔 | 2018 年 8 月 9 日 | 2,232.32 | 2,232.32

| ID | Symbol | Date        | Price     |
| 1  | DOW    | 08 Aug 2018 | 24,314.65 |
| 2  | DOW    | 09 Aug 2018 | 24,136.16 |
| 3  | S&P    | 08 Aug 2018 | 2,414.45  |
| 4  | S&P    | 09 Aug 2018 | 2,232.32  |

然而，基于列的物理数据库布局看起来完全不同。属于同一行的值紧密存储在一起：

However, the physical column-based database layout looks entirely different. Values belonging to the same row are stored closely together:

符号：1：DOW；2：陶氏化学；3：标准普尔；4：标准普尔
日期：2018年8月1:08；2018 年 8 月 2:09；2018 年 8 月 3:08；2018 年 8 月 4:09
价格：1:24,314.65；2:24,136.16；3:2,414.45；4:2,232.32

Symbol: 1:DOW; 2:DOW; 3:S&P; 4:S&P
Date:   1:08 Aug 2018; 2:09 Aug 2018; 3:08 Aug 2018; 4:09 Aug 2018
Price:  1:24,314.65; 2:24,136.16; 3:2,414.45; 4:2,232.32

为了重建数据元组（这可能对连接、过滤和多行聚合有用），我们需要在列级别保留一些元数据，以识别与其他列相关的数据点。如果显式执行此操作，每个值都必须保存一个键，这会引入重复并增加存储的数据量。一些列存储使用隐式标识符（虚拟 ID），并使用值的位置（换句话说，它的偏移量）将其映射回相关值[ABADI13]。

To reconstruct data tuples, which might be useful for joins, filtering, and multirow aggregates, we need to preserve some metadata on the column level to identify which data points from other columns it is associated with. If you do this explicitly, each value will have to hold a key, which introduces duplication and increases the amount of stored data. Some column stores use implicit identifiers (virtual IDs) instead and use the position of the value (in other words, its offset) to map it back to the related values [ABADI13].

在过去的几年中，可能是由于对不断增长的数据集运行复杂的分析查询的需求不断增长，我们已经看到许多新的面向列的文件格式，例如Apache Parquet、Apache ORC、RCFile，以及面向列的存储，例如Apache Kudu、ClickHouse等[ROY12]。

During the last several years, likely due to a rising demand to run complex analytical queries over growing datasets, we’ve seen many new column-oriented file formats such as Apache Parquet, Apache ORC, RCFile, as well as column-oriented stores, such as Apache Kudu, ClickHouse, and many others [ROY12].

区别与优化

Distinctions and Optimizations

仅仅说行存储和列存储之间的区别仅在于数据的存储方式是不够的。选择数据布局只是列式存储所针对的一系列可能优化的步骤之一。

It is not sufficient to say that distinctions between row and column stores are only in the way the data is stored. Choosing the data layout is just one of the steps in a series of possible optimizations that columnar stores are targeting.

在一次运行中读取同一列的多个值可显着提高缓存利用率和计算效率。在现代 CPU 上，矢量化指令可用于通过单个 CPU 指令³ [DREPPER07]处理多个数据点。

Reading multiple values for the same column in one run significantly improves cache utilization and computational efficiency. On modern CPUs, vectorized instructions can be used to process multiple data points with a single CPU instruction³ [DREPPER07].

将具有相同数据类型的值存储在一起（例如，数字与其他数字、字符串与其他字符串）可提供更好的压缩比。我们可以根据数据类型使用不同的压缩算法，并针对每种情况选择最有效的压缩方法。

Storing values that have the same data type together (e.g., numbers with other numbers, strings with other strings) offers a better compression ratio. We can use different compression algorithms depending on the data type and pick the most effective compression method for each case.

到决定是使用面向列的存储还是面向行的存储，您需要了解您的访问模式。如果读取的数据消耗在记录中（即请求大多数或所有列）并且工作负载主要由点查询和范围扫描组成，则面向行的方法可能会产生更好的结果。如果扫描跨越许多行，或者计算列子集上的聚合，则值得考虑面向列的方法。

To decide whether to use a column- or a row-oriented store, you need to understand your access patterns. If the read data is consumed in records (i.e., most or all of the columns are requested) and the workload consists mostly of point queries and range scans, the row-oriented approach is likely to yield better results. If scans span many rows, or compute aggregate over a subset of columns, it is worth considering a column-oriented approach.

宽列存储

Wide Column Stores

面向列的数据库不应与宽列存储混淆，例如BigTable或HBase，其中数据表示为多维映射，列被分组为列 族（通常存储相同类型的数据），并且在每个列族内部存储数据逐行。这种布局最适合存储通过一个键或一系列键检索的数据。

Column-oriented databases should not be mixed up with wide column stores, such as BigTable or HBase, where data is represented as a multidimensional map, columns are grouped into column families (usually storing data of the same type), and inside each column family, data is stored row-wise. This layout is best for storing data retrieved by a key or a sequence of keys.

Bigtable 论文[CHANG06]中的一个典型示例是 Webtable。Webtable 存储特定时间戳的网页内容、其属性以及它们之间的关系的快照。页面由反向 URL 标识，所有属性（例如页面内容和锚点，表示页面之间的链接）由拍摄这些快照的时间戳标识。简单地说，它可以表示为嵌套映射，如图1-3所示。

A canonical example from the Bigtable paper [CHANG06] is a Webtable. A Webtable stores snapshots of web page contents, their attributes, and the relations among them at a specific timestamp. Pages are identified by the reversed URL, and all attributes (such as page content and anchors, representing links between pages) are identified by the timestamps at which these snapshots were taken. In a simplified way, it can be represented as a nested map, as Figure 1-3 shows.

图 1-3。Webtable 的概念结构

数据存储在具有分层索引的多维排序映射中：我们可以通过反向 URL 定位与特定网页相关的数据，并通过时间戳定位其内容或锚点。每一行由其行键索引。相关列在列族中分组在一起（contents在anchor本例中），它们分别存储在磁盘上。列族中的每一列由列键标识，列键是列族名称和限定符（本例中为 , ）html的组合。列族按时间戳存储多个版本的数据。这种布局使我们能够快速找到更高级别的条目（在本例中为网页）及其参数（内容版本和其他页面的链接）。cnnsi.commy.look.ca

Data is stored in a multidimensional sorted map with hierarchical indexes: we can locate the data related to a specific web page by its reversed URL and its contents or anchors by the timestamp. Each row is indexed by its row key. Related columns are grouped together in column families—contents and anchor in this example—which are stored on disk separately. Each column inside a column family is identified by the column key, which is a combination of the column family name and a qualifier (html, cnnsi.com, my.look.ca in this example). Column families store multiple versions of data by timestamp. This layout allows us to quickly locate the higher-level entries (web pages, in this case) and their parameters (versions of content and links to the other pages).

虽然理解宽列存储的概念表示很有用，但它们的物理布局有些不同。列族中数据布局的示意图如图1-4所示：列族是分开存储的，但在每个列族中，属于同一键的数据存储在一起。

While it is useful to understand the conceptual representation of wide column stores, their physical layout is somewhat different. A schematic representation of the data layout in column families is shown in Figure 1-4: column families are stored separately, but in each column family, the data belonging to the same key is stored together.

图 1-4。网络表的物理结构

数据文件

Data Files

数据文件（有时称为主文件）可以实现为索引组织表（IOT）、堆组织表（堆文件）或散列组织表（散列文件）。

Data files (sometimes called primary files) can be implemented as index-organized tables (IOT), heap-organized tables (heap files), or hash-organized tables (hashed files).

堆文件中的记录不需要遵循任何特定的顺序，大多数情况下它们是按写入顺序放置的。这样，附加新页面时不需要额外的工作或文件重组。堆文件需要额外的索引结构，指向存储数据记录的位置，以使它们可搜索。

Records in heap files are not required to follow any particular order, and most of the time they are placed in a write order. This way, no additional work or file reorganization is required when new pages are appended. Heap files require additional index structures, pointing to the locations where data records are stored, to make them searchable.

在哈希文件中，记录存储在桶中，键的哈希值决定记录属于哪个桶。桶中的记录可以按附加顺序存储，也可以按键排序，以提高查找速度。

In hashed files, records are stored in buckets, and the hash value of the key determines which bucket a record belongs to. Records in the bucket can be stored in append order or sorted by key to improve lookup speed.

索引组织表 (IOT) 将数据记录存储在索引本身中。由于记录是按键顺序存储的，因此物联网中的范围扫描可以通过顺序扫描其内容来实现。

Index-organized tables (IOTs) store data records in the index itself. Since records are stored in key order, range scans in IOTs can be implemented by sequentially scanning its contents.

将数据记录存储在索引中可以使我们至少减少一次磁盘查找次数，因为在遍历索引并定位搜索到的键之后，我们不必寻址单独的文件来查找关联的数据记录。

Storing data records in the index allows us to reduce the number of disk seeks by at least one, since after traversing the index and locating the searched key, we do not have to address a separate file to find the associated data record.

当记录存储在单独的文件中时，索引文件保存数据条目，唯一标识数据记录并包含足够的信息来在数据文件中定位它们。例如，我们可以存储文件偏移量（有时称为行定位器）、数据文件中数据记录的位置，或者哈希文件中的存储桶 ID。在索引组织的表中，数据条目保存实际的数据记录。

When records are stored in a separate file, index files hold data entries, uniquely identifying data records and containing enough information to locate them in the data file. For example, we can store file offsets (sometimes called row locators), locations of data records in the data file, or bucket IDs in the case of hash files. In index-organized tables, data entries hold actual data records.

索引文件

Index Files

一个索引是一种以有利于高效检索操作的方式组织磁盘上数据记录的结构。索引文件被组织为专门的结构，将键映射到数据文件中存储由这些键（在堆文件的情况下）或主键（在索引组织表的情况下）标识的记录的位置。

An index is a structure that organizes data records on disk in a way that facilitates efficient retrieval operations. Index files are organized as specialized structures that map keys to locations in data files where the records identified by these keys (in the case of heap files) or primary keys (in the case of index-organized tables) are stored.

一个主（数据）文件上的索引称为主索引。但是，在大多数情况下，我们还可以假设主索引是基于主键或标识为主键的一组键构建的。所有其他索引都称为辅助索引。

An index on a primary (data) file is called the primary index. However, in most cases we can also assume that the primary index is built over a primary key or a set of keys identified as primary. All other indexes are called secondary.

二级索引可以直接指向数据记录，也可以简单地存储其主键。指向数据记录的指针可以保存堆文件或索引组织表的偏移量。多个二级索引可以指向同一条记录，从而允许单个数据记录通过不同的字段来标识并通过不同的索引进行定位。虽然主索引文件为每个搜索键保存一个唯一条目，但二级索引可以为每个搜索键保存多个条目[MOLINA08]。

Secondary indexes can point directly to the data record, or simply store its primary key. A pointer to a data record can hold an offset to a heap file or an index-organized table. Multiple secondary indexes can point to the same record, allowing a single data record to be identified by different fields and located through different indexes. While primary index files hold a unique entry per search key, secondary indexes may hold several entries per search key [MOLINA08].

如果数据记录的顺序遵循搜索键的顺序，这种索引称为聚簇（也称为聚类）。数据记录在集群情况下，通常存储在同一个文件或集群文件中，其中保留密钥顺序。如果数据存储在单独的文件中，并且其顺序不遵循密钥顺序，则索引称为非聚集索引（有时称为非聚集索引）。

If the order of data records follows the search key order, this index is called clustered (also known as clustering). Data records in the clustered case are usually stored in the same file or in a clustered file, where the key order is preserved. If the data is stored in a separate file, and its order does not follow the key order, the index is called nonclustered (sometimes called unclustered).

图 1-5显示了两种方法之间的差异：

Figure 1-5 shows the difference between the two approaches:

• a) 两个索引直接从二级索引文件引用数据条目。

• a) Two indexes reference data entries directly from secondary index files.

• b) 二级索引通过主索引的间接层来定位数据条目。

• b) A secondary index goes through the indirection layer of a primary index to locate the data entries.

图 1-5。将数据记录存储在索引文件中与存储数据文件的偏移量（索引段以白色显示；保存数据记录的段以灰色显示）

许多数据库系统有一个固有的和显式的主键，一组唯一标识数据库记录的列。在未指定主键的情况下，存储引擎可以创建隐式主键（例如MySQL InnoDB添加新的自增列并自动填充其值）。

Many database systems have an inherent and explicit primary key, a set of columns that uniquely identify the database record. In cases when the primary key is not specified, the storage engine can create an implicit primary key (for example, MySQL InnoDB adds a new auto-increment column and fills in its values automatically).

这个术语用于不同类型的数据库系统：关系数据库系统（例如 MySQL 和 PostgreSQL）、基于 Dynamo 的 NoSQL 存储（例如Apache Cassandra和Riak）以及文档存储（例如 MongoDB）。可能有一些特定于项目的命名，但大多数情况下，该术语都有明确的映射。

This terminology is used in different kinds of database systems: relational database systems (such as MySQL and PostgreSQL), Dynamo-based NoSQL stores (such as Apache Cassandra and in Riak), and document stores (such as MongoDB). There can be some project-specific naming, but most often there’s a clear mapping to this terminology.

主索引作为间接索引

Primary Index as an Indirection

对于是否可以，数据库界有不同的意见。数据记录应直接引用（通过文件偏移量）或通过主键索引引用。⁴

There are different opinions in the database community on whether data records should be referenced directly (through file offset) or via the primary key index.⁴

两种方法都有其优点和缺点，并且可以在完整实施的范围内更好地讨论。通过直接引用数据，我们可以减少磁盘寻道次数，但在维护过程中每当更新或重新定位记录时都必须付出更新指针的成本。使用主索引形式的间接允许我们减少指针更新的成本，但在读取路径上的成本较高。

Both approaches have their pros and cons and are better discussed in the scope of a complete implementation. By referencing data directly, we can reduce the number of disk seeks, but have to pay a cost of updating the pointers whenever the record is updated or relocated during a maintenance process. Using indirection in the form of a primary index allows us to reduce the cost of pointer updates, but has a higher cost on a read path.

如果工作负载主要由读取组成，则仅更新几个索引可能会起作用，但这种方法不适用于具有多个索引的写入密集型工作负载。为了降低指针更新的成本，一些实现使用主键来代替有效负载偏移量来进行间接寻址。例如，MySQL InnoDB 使用主索引并执行两次查找：执行查询时，一次在辅助索引中查找，一次在主索引中查找[TARIQ11]。这会增加主索引查找的开销，而不是直接跟踪辅助索引的偏移量。

Updating just a couple of indexes might work if the workload mostly consists of reads, but this approach does not work well for write-heavy workloads with multiple indexes. To reduce the costs of pointer updates, instead of payload offsets, some implementations use primary keys for indirection. For example, MySQL InnoDB uses a primary index and performs two lookups: one in the secondary index, and one in a primary index when performing a query [TARIQ11]. This adds an overhead of a primary index lookup instead of following the offset directly from the secondary index.

图 1-6显示了这两种方法的不同之处：

Figure 1-6 shows how the two approaches are different:

• a) 两个索引直接从二级索引文件引用数据条目。

• a) Two indexes reference data entries directly from secondary index files.

• b) 二级索引通过主索引的间接层来定位数据条目。

• b) A secondary index goes through the indirection layer of a primary index to locate the data entries.

图 1-6。直接引用数据元组 (a) 与使用主索引作为间接引用(b)

还可以使用混合方法并存储数据文件偏移量和主键。首先，检查数据偏移量是否仍然有效，并支付额外的成本来检查主键索引（如果已更改），并在找到新的偏移量后更新索引文件。

It is also possible to use a hybrid approach and store both data file offsets and primary keys. First, you check if the data offset is still valid and pay the extra cost of going through the primary key index if it has changed, updating the index file after finding a new offset.

固态硬盘

Solid State Drives

固态硬盘 (SSD)没有移动部件：没有旋转的磁盘，也没有必须定位的磁头以供读取。典型的 SSD 由存储单元组成，连接成串（通常每个串 32 到 64 个单元），串组合成数组，数组组合成页，页组合成块 [LARRIVEE15]。

Solid state drives (SSDs) do not have moving parts: there’s no disk that spins, or head that has to be positioned for the read. A typical SSD is built of memory cells, connected into strings (typically 32 to 64 cells per string), strings are combined into arrays, arrays are combined into pages, and pages are combined into blocks [LARRIVEE15].

根据所使用的具体技术，单元可以保存一位或多位数据。页面大小因设备而异，但通常大小范围为 2 到 16 Kb。块通常包含 64 到 512 页。块被组织成平面，最后，平面被放置在一个死。SSD 可以有一个或多个芯片。图 2-5显示了该层次结构。

Depending on the exact technology used, a cell can hold one or multiple bits of data. Pages vary in size between devices, but typically their sizes range from 2 to 16 Kb. Blocks typically contain 64 to 512 pages. Blocks are organized into planes and, finally, planes are placed on a die. SSDs can have one or more dies. Figure 2-5 shows this hierarchy.

图 2-5。SSD组织示意图

可以写入（编程）或读取的最小单位是页。然而，我们只能对空的存储单元进行更改（即，在写入之前已被擦除的存储单元）。最小的擦除实体不是一个页面，而是一个包含多个页面的块，这就是为什么它通常被称为擦除块。空块中的页必须按顺序写入。

The smallest unit that can be written (programmed) or read is a page. However, we can only make changes to the empty memory cells (i.e., to ones that have been erased before the write). The smallest erase entity is not a page, but a block that holds multiple pages, which is why it is often called an erase block. Pages in an empty block have to be written sequentially.

这闪存控制器的一部分，负责将页面 ID 映射到其物理位置，跟踪空页面、写入页面和丢弃页面，称为闪存转换层 (FTL)（有关 FTL 的更多信息，请参阅“闪存转换层” ）。它还负责垃圾收集，在此期间 FTL 找到可以安全擦除的块。某些块可能仍包含活动页面。在这种情况下，它将活动页面从这些块重新定位到新位置，并重新映射页面 ID 以指向那里。此后，它会擦除​​现在未使用的块，使它们可用于写入。

The part of a flash memory controller responsible for mapping page IDs to their physical locations, tracking empty, written, and discarded pages, is called the Flash Translation Layer (FTL) (see “Flash Translation Layer” for more about FTL). It is also responsible for garbage collection, during which FTL finds blocks it can safely erase. Some blocks might still contain live pages. In this case, it relocates live pages from these blocks to new locations and remaps page IDs to point there. After this, it erases the now-unused blocks, making them available for writes.

自从在两种设备类型（HDD 和 SSD）中，我们正在寻址内存块而不是单个字节（即按块访问数据），大多数操作系统都有块设备抽象[CESATI05]。它隐藏内部磁盘结构并在内部缓冲 I/O 操作，因此当我们从块设备读取单个字时，会读取包含该字的整个块。这是一个我们不能忽视的约束，并且在使用磁盘驻留数据结构时应该始终考虑到这一点。

Since in both device types (HDDs and SSDs) we are addressing chunks of memory rather than individual bytes (i.e., accessing data block-wise), most operating systems have a block device abstraction [CESATI05]. It hides an internal disk structure and buffers I/O operations internally, so when we’re reading a single word from a block device, the whole block containing it is read. This is a constraint we cannot ignore and should always take into account when working with disk-resident data structures.

在SSD中，我们并没有特别强调随机 I/O 与顺序 I/O（如 HDD），因为随机读取和顺序读取之间的延迟差异不大。预取、读取连续页和内部并行性仍然存在一些差异[GOOSSAERT14]。

In SSDs, we don’t have a strong emphasis on random versus sequential I/O, as in HDDs, because the difference in latencies between random and sequential reads is not as large. There is still some difference caused by prefetching, reading contiguous pages, and internal parallelism [GOOSSAERT14].

尽管垃圾收集通常是后台操作，但其影响可能会对写入性能产生负面影响，特别是在随机和未对齐写入工作负载的情况下。

Even though garbage collection is usually a background operation, its effects may negatively impact write performance, especially in cases of random and unaligned write workloads.

仅写入完整块，并将后续写入组合到同一块，有助于减少所需 I/O 操作的数量。我们将在后面的章节中讨论缓冲和不变性作为实现这一目标的方法。

Writing only full blocks, and combining subsequent writes to the same block, can help to reduce the number of required I/O operations. We discuss buffering and immutability as ways to achieve that in later chapters.

磁盘结构

On-Disk Structures

除了磁盘访问本身的成本，构建高效磁盘结构的主要限制和设计条件是磁盘操作的最小单位是块。为了跟随指针指向块内的特定位置，我们必须获取整个块。由于我们已经必须这样做，因此我们可以更改数据结构的布局以利用它。

Besides the cost of disk access itself, the main limitation and design condition for building efficient on-disk structures is the fact that the smallest unit of disk operation is a block. To follow a pointer to the specific location within the block, we have to fetch an entire block. Since we already have to do that, we can change the layout of the data structure to take advantage of it.

我们已经在本章中多次提到了指针，但是这个词对于磁盘结构的语义略有不同。在磁盘上，大多数时候我们手动管理数据布局（除非，例如，我们使用内存映射文件）。这仍然与常规指针操作类似，但我们必须计算目标指针地址并显式地跟踪指针。

We’ve mentioned pointers several times throughout this chapter already, but this word has slightly different semantics for on-disk structures. On disk, most of the time we manage the data layout manually (unless, for example, we’re using memory mapped files). This is still similar to regular pointer operations, but we have to compute the target pointer addresses and follow the pointers explicitly.

大多数时候，磁盘上的偏移量是预先计算的（在指针在其指向的部分之前写入磁盘的情况下）或缓存在内存中，直到它们刷新到磁盘上。在磁盘结构中创建长依赖链会大大增加代码和结构的复杂性，因此最好将指针的数量及其跨度保持在最低限度。

Most of the time, on-disk offsets are precomputed (in cases when the pointer is written on disk before the part it points to) or cached in memory until they are flushed on the disk. Creating long dependency chains in on-disk structures greatly increases code and structure complexity, so it is preferred to keep the number of pointers and their spans to a minimum.

总之，磁盘结构的设计考虑了其目标存储细节，并且通常针对更少的磁盘访问进行优化。我们可以通过提高局部性、优化结构的内部表示以及减少页外指针的数量来实现这一点。

In summary, on-disk structures are designed with their target storage specifics in mind and generally optimize for fewer disk accesses. We can do this by improving locality, optimizing the internal representation of the structure, and reducing the number of out-of-page pointers.

在“二叉搜索树”中，我们得出结论高扇出和低高度是最佳磁盘数据结构所需的属性。我们还刚刚讨论了来自指针的额外空间开销，以及由于平衡而重新映射这些指针所带来的维护开销。B-Tree 结合了这些思想：增加节点扇出，并减少树高、节点指针的数量和平衡操作的频率。

In “Binary Search Trees”, we came to the conclusion that high fanout and low height are desired properties for an optimal on-disk data structure. We’ve also just discussed additional space overhead coming from pointers, and maintenance overhead from remapping these pointers as a result of balancing. B-Trees combine these ideas: increase node fanout, and reduce tree height, the number of node pointers, and the frequency of balancing operations.

B树层次结构

B-Tree Hierarchy

B树由多个节点组成。每个节点都保存指向子节点的N键和指针。N + 1这些节点在逻辑上分为三组：

B-Trees consist of multiple nodes. Each node holds up to N keys and N + 1 pointers to the child nodes. These nodes are logically grouped into three groups:

根节点

Root node

这没有父母，是树的顶端。

This has no parents and is the top of the tree.

叶节点

Leaf nodes

这些是没有子节点的底层节点。

These are the bottom layer nodes that have no child nodes.

内部节点

Internal nodes

这些是所有其他节点，连接根和叶子。通常有不止一级的内部节点。

These are all other nodes, connecting root with leaves. There is usually more than one level of internal nodes.

该层次结构如图 2-9所示。

This hierarchy is shown in Figure 2-9.

图 2-9。B-Tree 节点层次结构

由于 B 树是作为一种页面组织技术（即，它们用于组织和导航固定大小的页面），我们经常互换使用术语“节点”和“页面”。

Since B-Trees are a page organization technique (i.e., they are used to organize and navigate fixed-size pages), we often use terms node and page interchangeably.

这节点容量与其实际持有的密钥数量之间的关系称为占用率。

The relation between the node capacity and the number of keys it actually holds is called occupancy.

B树其特征在于它们的扇出：每个节点中存储的密钥数量。较高的扇出有助于分摊保持树平衡所需的结构更改的成本，并通过将指向子节点的键和指针存储在单个块或多个连续块中来减少查找次数。平衡运营当节点已满或几乎为空时，会触发（即拆分和合并）。

B-Trees are characterized by their fanout: the number of keys stored in each node. Higher fanout helps to amortize the cost of structural changes required to keep the tree balanced and to reduce the number of seeks by storing keys and pointers to child nodes in a single block or multiple consecutive blocks. Balancing operations (namely, splits and merges) are triggered when the nodes are full or nearly empty.

分隔键

Separator Keys

已存储钥匙B 树中的节点称为索引条目、分隔符键或分隔符单元。他们将树拆分为子树（也称为分支或子范围），并保存相应的键范围。键按排序顺序存储，以便进行二分搜索。通过定位键并跟随相应的指针从较高层到较低层来找到子树。

Keys stored in B-Tree nodes are called index entries, separator keys, or divider cells. They split the tree into subtrees (also called branches or subranges), holding corresponding key ranges. Keys are stored in sorted order to allow binary search. A subtree is found by locating a key and following a corresponding pointer from the higher to the lower level.

节点中的第一个指针指向保存小于第一个键的项的子树，节点中的最后一个指针指向保存大于或等于最后一个键的项的子树。其他指针是两个键之间的引用子树： ，其中是一组键，是属于该子树的键。图 2-10显示了这些不变量。Ki-1 ≤ Ks < KiKKs

The first pointer in the node points to the subtree holding items less than the first key, and the last pointer in the node points to the subtree holding items greater than or equal to the last key. Other pointers are reference subtrees between the two keys: Ki-1 ≤ Ks < Ki, where K is a set of keys, and Ks is a key that belongs to the subtree. Figure 2-10 shows these invariants.

图 2-10。分隔符键如何将树拆分为子树

一些 B 树变体还具有同级节点指针，通常位于叶级别，以简化范围扫描。这些指针有助于避免返回父级来查找下一个兄弟姐妹。一些实现具有双向指针，在叶级别形成双链表，这使得反向迭代成为可能。

Some B-Tree variants also have sibling node pointers, most often on the leaf level, to simplify range scans. These pointers help avoid going back to the parent to find the next sibling. Some implementations have pointers in both directions, forming a double-linked list on the leaf level, which makes the reverse iteration possible.

B 树的与众不同之处在于，它们不是从上到下构建的（如二叉搜索树），而是相反的方式构建——从下到上。叶节点的数量增加，从而增加了内部节点的数量和树的高度。

What sets B-Trees apart is that, rather than being built from top to bottom (as binary search trees), they’re constructed the other way around—from bottom to top. The number of leaf nodes grows, which increases the number of internal nodes and tree height.

由于 B 树在节点内保留额外空间以供将来插入和更新，因此树存储利用率可低至 50%，但通常要高得多。较高的占用率不会对 B-Tree 性能产生负面影响。

Since B-Trees reserve extra space inside nodes for future insertions and updates, tree storage utilization can get as low as 50%, but is usually considerably higher. Higher occupancy does not influence B-Tree performance negatively.

B 树查找复杂度

B-Tree Lookup Complexity

B树查找复杂性可以从两个角度来看：块传输的数量和查找期间完成的比较的数量。

B-Tree lookup complexity can be viewed from two standpoints: the number of block transfers and the number of comparisons done during the lookup.

就传输数量而言，对数底为N（每个节点的密钥数量）。每个新级别上都有K更多的节点，并且跟随子指针会减少 的搜索空间N。在查找过程中，最多（其中是 B 树中的项目总数）页被寻址以查找搜索到的键。从根到叶的传递必须遵循的子指针的数量也等于层数，换句话说，就是树的高度。logK MMh

In terms of number of transfers, the logarithm base is N (number of keys per node). There are K times more nodes on each new level, and following a child pointer reduces the search space by the factor of N. During lookup, at most logK M (where M is a total number of items in the B-Tree) pages are addressed to find a searched key. The number of child pointers that have to be followed on the root-to-leaf pass is also equal to the number of levels, in other words, the height h of the tree.

从比较次数的角度来看，对数底是2，因为在每个节点内搜索键是使用二分搜索完成的。每次比较都会将搜索空间减半，因此复杂度为。log2 M

From the perspective of number of comparisons, the logarithm base is 2, since searching a key inside each node is done using binary search. Every comparison halves the search space, so complexity is log2 M.

了解查找次数和比较次数之间的区别有助于我们直观地了解搜索是如何执行的，并从两个角度理解什么是查找复杂性。

Knowing the distinction between the number of seeks and the number of comparisons helps us gain the intuition about how searches are performed and understand what lookup complexity is, from both perspectives.

在教科书和文章中，² B 树查找复杂度通常被称为log M。对数底数通常不用于复杂性分析，因为改变底数只是添加一个常数因子，而乘以一个常数因子不会改变复杂性。例如，给定非零常数因子c，O(|c| × n) == O(n) [KNUTH97]。

In textbooks and articles,² B-Tree lookup complexity is generally referenced as log M. Logarithm base is generally not used in complexity analysis, since changing the base simply adds a constant factor, and multiplication by a constant factor does not change complexity. For example, given the nonzero constant factor c, O(|c| × n) == O(n) [KNUTH97].

B树查找算法

B-Tree Lookup Algorithm

现在我们已经介绍了 B 树的结构和内部组织，我们可以定义查找、插入和删除的算法。要在 B 树中查找项目，我们必须执行从根到叶的单次遍历。此搜索的目的是找到搜索到的关键字或其前身。查找精确匹配用于点查询、更新和删除；找到它的前身对于范围扫描和插入很有用。

Now that we have covered the structure and internal organization of B-Trees, we can define algorithms for lookups, insertions, and removals. To find an item in a B-Tree, we have to perform a single traversal from root to leaf. The objective of this search is to find a searched key or its predecessor. Finding an exact match is used for point queries, updates, and deletions; finding its predecessor is useful for range scans and inserts.

该算法从根节点开始，执行二分查找，将搜索到的键与根节点中存储的键进行比较，直到找到第一个大于搜索值的分隔符键。这将定位搜索到的子树。正如我们之前讨论的，索引键将树分割成子树，子树的边界位于两个相邻键之间。一旦找到子树，我们就沿着与其对应的指针继续相同的搜索过程（找到分隔符键，沿着指针），直到到达目标叶节点，在那里我们找到搜索到的键或得出结论通过查找其前身不存在。

The algorithm starts from the root and performs a binary search, comparing the searched key with the keys stored in the root node until it finds the first separator key that is greater than the searched value. This locates a searched subtree. As we’ve discussed previously, index keys split the tree into subtrees with boundaries between two neighboring keys. As soon as we find the subtree, we follow the pointer that corresponds to it and continue the same search process (locate the separator key, follow the pointer) until we reach a target leaf node, where we either find the searched key or conclude it is not present by locating its predecessor.

在每个级别上，我们都会获得树的更详细视图：我们从最粗粒度的级别（树的根）开始，然后下降到下一个级别，其中键代表更精确、详细的范围，直到我们最终到达叶子，数据记录所在的位置。

On each level, we get a more detailed view of the tree: we start on the most coarse-grained level (the root of the tree) and descend to the next level where keys represent more precise, detailed ranges, until we finally reach leaves, where the data records are located.

点查询时，在找到或者没有找到所查找的key后进行查找。在范围扫描期间，迭代从最接近的找到的键值对开始，并通过跟随兄弟指针继续，直到到达范围的末尾或范围谓词耗尽。

During the point query, the search is done after finding or failing to find the searched key. During the range scan, iteration starts from the closest found key-value pair and continues by following sibling pointers until the end of the range is reached or the range predicate is exhausted.

计算按键

Counting Keys

穿过在文献中，您可以找到不同的方法来描述键和子偏移量计数。[BAYER72]k提到了代表最佳页面大小的与设备相关的自然数。在这种情况下，页面可以在k和2k键之间保存，但可以部分填充并保存至少k + 1且最多2k + 1指向子节点的指针。根页面可以容纳1和2k键之间。后来l引入了一个数字，据说任何非叶页都可以有l + 1键。

Across the literature, you can find different ways to describe key and child offset counts. [BAYER72] mentions the device-dependent natural number k that represents an optimal page size. Pages, in this case, can hold between k and 2k keys, but can be partially filled and hold at least k + 1 and at most 2k + 1 pointers to child nodes. The root page can hold between 1 and 2k keys. Later, a number l is introduced, and it is said that any nonleaf page can have l + 1 keys.

其他源，例如[GRAEFE11]，描述了可以容纳N 分隔符键和N + 1 指针的节点，具有其他相似的语义和不变量。

Other sources, for example [GRAEFE11], describe nodes that can hold up to N separator keys and N + 1 pointers, with otherwise similar semantics and invariants.

两种方法都给我们带来相同的结果，差异只是为了强调每个来源的内容。为了清楚起见，在本书中，我们坚持使用N键（或键值对，在叶节点的情况下）的数量。

Both approaches bring us to the same result, and differences are only used to emphasize the contents of each source. In this book, we stick to N as the number of keys (or key-value pairs, in the case of the leaf nodes) for clarity.

B 树节点分裂

B-Tree Node Splits

到将值插入 B 树时，我们首先必须找到目标叶子并找到插入点。为此，我们使用上一节中描述的算法。找到叶子后，会将键和值附加到其上。B 树中的更新通过使用查找算法定位目标叶节点并将新值与现有键相关联来工作。

To insert the value into a B-Tree, we first have to locate the target leaf and find the insertion point. For that, we use the algorithm described in the previous section. After the leaf is located, the key and value are appended to it. Updates in B-Trees work by locating a target leaf node using a lookup algorithm and associating a new value with an existing key.

如果目标节点没有足够的可用空间，我们说该节点已溢出 [NICHOLS66]，必须分成两部分以适应新数据。更准确地说，如果满足以下条件，则节点将被分裂：

If the target node doesn’t have enough room available, we say that the node has overflowed [NICHOLS66] and has to be split in two to fit the new data. More precisely, the node is split if the following conditions hold:

• 对于叶子节点：如果该节点可以容纳最多个N键值对，那么再插入一个键值对就会超过其最大容量N。

• For leaf nodes: if the node can hold up to N key-value pairs, and inserting one more key-value pair brings it over its maximum capacity N.

• 对于非叶节点：如果该节点可以容纳N + 1指针，那么再插入一个指针就会使其超过其最大容量N + 1。

• For nonleaf nodes: if the node can hold up to N + 1 pointers, and inserting one more pointer brings it over its maximum capacity N + 1.

分裂是通过分配新节点、将分裂节点的一半元素转移到新节点、并将其第一个键和指向父节点的指针添加来完成的。在这种情况下，我们说关键是晋升。执行分割的索引称为分割点（也称为中点）。分裂点之后的所有元素（包括非叶节点分裂情况下的分裂点）都转移到新创建的兄弟节点，其余元素保留在分裂节点中。

Splits are done by allocating the new node, transferring half the elements from the splitting node to it, and adding its first key and pointer to the parent node. In this case, we say that the key is promoted. The index at which the split is performed is called the split point (also called the midpoint). All elements after the split point (including split point in the case of nonleaf node split) are transferred to the newly created sibling node, and the rest of the elements remain in the splitting node.

如果父节点已满并且没有空间可用于提升的键和指向新创建节点的指针，则它也必须被拆分。此操作可能会递归地一直传播到根。

If the parent node is full and does not have space available for the promoted key and pointer to the newly created node, it has to be split as well. This operation might propagate recursively all the way to the root.

一旦树达到其容量（即，分裂一直传播到根），我们就必须分裂根节点。当根节点被分裂时，会分配一个持有分裂点密钥的新根。旧的根（现在只保存一半的条目）与其新创建的同级一起被降级到下一个级别，从而将树的高度增加一倍。当根节点被分裂并分配新的根时，或者当两个节点合并形成新的根时，树的高度会发生变化。在叶子和内部节点级别上，树仅水平生长。

As soon as the tree reaches its capacity (i.e., split propagates all the way up to the root), we have to split the root node. When the root node is split, a new root, holding a split point key, is allocated. The old root (now holding only half the entries) is demoted to the next level along with its newly created sibling, increasing the tree height by one. The tree height changes when the root node is split and the new root is allocated, or when two nodes are merged to form a new root. On the leaf and internal node levels, the tree only grows horizontally.

图 2-11显示了插入新元素期间完全被占用的叶11节点。我们在完整节点的中间画一条线，将一半元素保留在节点中，并将其余元素移动到新节点。分割点值被放置到父节点中作为分隔符键。

Figure 2-11 shows a fully occupied leaf node during insertion of the new element 11. We draw the line in the middle of the full node, leave half the elements in the node, and move the rest of elements to the new one. A split point value is placed into the parent node to serve as a separator key.

图 2-11。插入期间叶节点分裂11。新元素和升级的键以灰色显示。

图2-12显示了一个完全占用的非叶节点（即根节点或内部节点）在插入新元素时的分裂过程11。要执行拆分，我们首先创建一个新节点并将从索引开始的元素移动N/2 + 1到该节点。分割点密钥被提升到父级。

Figure 2-12 shows the split process of a fully occupied nonleaf (i.e., root or internal) node during insertion of the new element 11. To perform a split, we first create a new node and move elements starting from index N/2 + 1 to it. The split point key is promoted to the parent.

图 2-12。插入期间非叶节点分裂11。新元素和升级的键以灰色显示。

由于非叶节点分裂始终是从下面的级别传播的分裂的表现，因此我们有一个额外的指针（指向下一层新创建的节点）。如果父级没有足够的空间，则也必须将其拆分。

Since nonleaf node splits are always a manifestation of splits propagating from the levels below, we have an additional pointer (to the newly created node on the next level). If the parent does not have enough space, it has to be split as well.

叶节点或非叶节点是否被拆分（即节点是否保存键和值或仅保存键）并不重要。在叶分割的情况下，键与其关联的值一起移动。

It doesn’t matter whether the leaf or nonleaf node is split (i.e., whether the node holds keys and values or just the keys). In the case of leaf split, keys are moved together with their associated values.

分割完成后，我们有两个节点，必须选择正确的一个才能完成插入。为此，我们可以使用分隔符键不变量。如果插入的键小于提升的键，我们通过插入到分裂节点来完成操作。否则，我们将插入到新创建的中。

When the split is done, we have two nodes and have to pick the correct one to finish insertion. For that, we can use the separator key invariants. If the inserted key is less than the promoted one, we finish the operation by inserting to the split node. Otherwise, we insert to the newly created one.

总而言之，节点分裂分四个步骤完成：

To summarize, node splits are done in four steps:

1. 分配一个新节点。

2. Allocate a new node.

3. 将分裂节点的一半元素复制到新节点。

4. Copy half the elements from the splitting node to the new one.

5. 将新元素放入相应的节点中。

6. Place the new element into the corresponding node.

7. 在分割节点的父节点处，添加分隔符键和指向新节点的指针。

8. At the parent of the split node, add a separator key and a pointer to the new node.

B 树节点合并

B-Tree Node Merges

删除通过首先定位目标叶子来完成。当找到叶子时，与其关联的键和值将被删除。

Deletions are done by first locating the target leaf. When the leaf is located, the key and the value associated with it are removed.

如果相邻节点的值太少（即，它们的占用率低于阈值），则合并兄弟节点。这这种情况称为下溢。[BAYER72]描述了两种下溢场景：如果两个相邻节点有一个共同的父节点并且它们的内容适合单个节点，则它们的内容应该被合并（连接）；如果它们的内容不适合单个节点，则会在它们之间重新分配密钥以恢复平衡（请参阅“重新平衡”）。更准确地说，如果满足以下条件，则两个节点将被合并：

If neighboring nodes have too few values (i.e., their occupancy falls under a threshold), the sibling nodes are merged. This situation is called underflow. [BAYER72] describes two underflow scenarios: if two adjacent nodes have a common parent and their contents fit into a single node, their contents should be merged (concatenated); if their contents do not fit into a single node, keys are redistributed between them to restore balance (see “Rebalancing”). More precisely, two nodes are merged if the following conditions hold:

• 对于叶子节点：如果一个节点最多可以容纳N键值对，并且两个相邻节点的键值对数量之和小于或等于N。

• For leaf nodes: if a node can hold up to N key-value pairs, and a combined number of key-value pairs in two neighboring nodes is less than or equal to N.

• 对于非叶节点：如果一个节点最多可以容纳N + 1指针，并且两个相邻节点的指针数量之和小于或等于N + 1。

• For nonleaf nodes: if a node can hold up to N + 1 pointers, and a combined number of pointers in two neighboring nodes is less than or equal to N + 1.

图 2-13显示了删除 element 期间的合并16。为此，我们将元素从一个兄弟姐妹移动到另一个兄弟姐妹。通常，右侧同级的元素会移动到左侧，但只要保留键顺序，也可以以相反的方式完成。

Figure 2-13 shows the merge during deletion of element 16. To do this, we move elements from one of the siblings to the other one. Generally, elements from the right sibling are moved to the left one, but it can be done the other way around as long as the key order is preserved.

图 2-13。叶节点合并

图 2-14显示了在删除 element 期间必须合并的两个兄弟非叶节点10。如果我们将它们的元素组合起来，它们就会适合一个节点，因此我们可以有一个节点而不是两个。在合并非叶节点期间，我们必须从父节点中提取相应的分隔符键（即，将其降级）。指针的数量减少了 1，因为合并是由页面删除引起的指针删除从较低级别传播的结果。就像拆分一样，合并可以一直传播到根级别。

Figure 2-14 shows two sibling nonleaf nodes that have to be merged during deletion of element 10. If we combine their elements, they fit into one node, so we can have one node instead of two. During the merge of nonleaf nodes, we have to pull the corresponding separator key from the parent (i.e., demote it). The number of pointers is reduced by one because the merge is a result of the propagation of the pointer deletion from the lower level, caused by the page removal. Just as with splits, merges can propagate all the way to the root level.

图 2-14。非叶节点合并

总而言之，假设元素已被删除，节点合并分三个步骤完成：

To summarize, node merges are done in three steps, assuming the element is already removed:

1. 将右侧节点的所有元素复制到左侧节点。

2. Copy all elements from the right node to the left one.

3. 从父节点中删除右节点指针（或者在非叶合并的情况下将其降级）。

4. Remove the right node pointer from the parent (or demote it in the case of a nonleaf merge).

5. 删除右侧节点。

6. Remove the right node.

在 B 树中经常实现的用于减少拆分和合并次数的技术之一是重新平衡，我们将在“重新平衡”中讨论该技术。

One of the techniques often implemented in B-Trees to reduce the number of splits and merges is rebalancing, which we discuss in “Rebalancing”.

原始类型

Primitive Types

键和值具有类型，例如integer、date、 或string，并且可以以其原始二进制形式表示（序列化和反序列化）。

Keys and values have a type, such as integer, date, or string, and can be represented (serialized to and deserialized from) in their raw binary forms.

大多数数值数据类型都表示为固定大小的值。当使用多字节数值时，使用编码和解码的字节顺序（字节序）相同。Endianness 决定字节的顺序：

Most numeric data types are represented as fixed-size values. When working with multibyte numeric values, it is important to use the same byte-order (endianness) for both encoding and decoding. Endianness determines the sequential order of bytes:

大尾数

Big-endian

这订单从最高有效字节 (MSB)，后面是按重要性递减顺序排列的字节。换句话说，MSB 具有最低地址。

The order starts from the most-significant byte (MSB), followed by the bytes in decreasing significance order. In other words, MSB has the lowest address.

小尾数法

Little-endian

这顺序从最低有效字节 (LSB) 开始，后面跟着按重要性递增的顺序排列的字节。

The order starts from the least-significant byte (LSB), followed by the bytes in increasing significance order.

图 3-1说明了这一点。十六进制 32 位整数0xAABBCCDD，其中AA是 MSB，使用大端和小端字节顺序显示。

Figure 3-1 illustrates this. The hexadecimal 32-bit integer 0xAABBCCDD, where AA is the MSB, is shown using both big- and little-endian byte order.

图 3-1。大端和小端字节顺序。最高有效字节以灰色显示。地址（用 表示）a从左向右增长。

例如，要重建具有相应字节顺序的 64 位整数，RocksDB 具有特定于平台的定义，有助于识别目标平台字节顺序。¹如果目标平台字节序与值字节序不匹配（EncodeFixed64WithEndian查找kLittleEndian值并将其与值字节序进行比较），则使用 反转字节EndianTransform，以相反的顺序按字节读取值并将它们附加到结果中。

For example, to reconstruct a 64-bit integer with a corresponding byte order, RocksDB has platform-specific definitions that help to identify target platform byte order.¹ If the target platform endianness does not match value endianness (EncodeFixed64WithEndian looks up kLittleEndian value and compares it with value endianness), it reverses the bytes using EndianTransform, which reads values byte-wise in reverse order and appends them to the result.

记录由数字、字符串、布尔值及其组合等基元组成。然而，当通过网络传输数据或将其存储在磁盘上时，我们只能使用字节序列。这意味着，为了发送或写入记录，我们必须序列化它（将其转换为可解释的字节序列），并且在接收或读取后使用它之前，我们有反序列化它（将字节序列转换回原始记录）。

Records consist of primitives like numbers, strings, booleans, and their combinations. However, when transferring data over the network or storing it on disk, we can only use byte sequences. This means that, in order to send or write the record, we have to serialize it (convert it to an interpretable sequence of bytes) and, before we can use it after receiving or reading, we have to deserialize it (translate the sequence of bytes back to the original record).

在二进制数据格式中，我们总是从用作更复杂结构构建块的基元开始。不同的数字类型的大小可能不同。byte值是 8 位、short2 字节（16 位）、int4 字节（32 位）、long8 字节（64 位）。

In binary data formats, we always start with primitives that serve as building blocks for more complex structures. Different numeric types may vary in size. byte value is 8 bits, short is 2 bytes (16 bits), int is 4 bytes (32 bits), and long is 8 bytes (64 bits).

浮点数字（例如float和）由它们的符号、分数和指数double表示。IEEE 二进制浮点运算标准( IEEE 754) 标准描述了广泛接受的浮点数表示形式。32 位表示单精度值。例如，浮点数具有二进制表示形式，如图3-2所示。前23位表示分数，后面8位表示指数，1位表示符号（无论数字是否为负）。float0.15652

Floating-point numbers (such as float and double) are represented by their sign, fraction, and exponent. The IEEE Standard for Binary Floating-Point Arithmetic (IEEE 754) standard describes widely accepted floating-point number representation. A 32-bit float represents a single-precision value. For example, a floating-point number 0.15652 has a binary representation, as shown in Figure 3-2. The first 23 bits represent a fraction, the following 8 bits represent an exponent, and 1 bit represents a sign (whether or not the number is negative).

图 3-2。单精度浮点数的二进制表示

由于浮点值是使用分数计算的，因此该表示产生的数字只是一个近似值。讨论完整的转换算法超出了本书的范围，我们只讨论表示基础知识。

Since a floating-point value is calculated using fractions, the number this representation yields is just an approximation. Discussing a complete conversion algorithm is out of the scope of this book, and we only cover representation basics.

表示double双精度浮点值[SAVARD05]。大多数编程语言都具有对浮点​​值与其标准库中的二进制表示进行编码和解码的方法。

The double represents a double-precision floating-point value [SAVARD05]. Most programming languages have means for encoding and decoding floating-point values to and from their binary representation in their standard libaries.

字符串和可变大小的数据

Strings and Variable-Size Data

全部原始数字类型具有固定大小。将更复杂的值组合在一起很像C 中的struct^{2。您可以将原始值组合成结构并使用固定大小的数组或指向其他内存区域的指针。}

All primitive numeric types have a fixed size. Composing more complex values together is much like struct² in C. You can combine primitive values into structures and use fixed-size arrays or pointers to other memory regions.

字符串和其他可变大小的数据类型（例如固定大小数据的数组）可以序列化为数字，表示数组或字符串的长度，后跟字节size：实际数据。对于字符串，这种表示形式通常称为UCSD String或Pascal String，以 Pascal 编程语言的流行实现命名。我们可以用伪代码表示如下：

Strings and other variable-size data types (such as arrays of fixed-size data) can be serialized as a number, representing the length of the array or string, followed by size bytes: the actual data. For strings, this representation is often called UCSD String or Pascal String, named after the popular implementation of the Pascal programming language. We can express it in pseudocode as follows:

细绳
{
    大小 uint_16
    数据字节[大小]
}

String
{
    size    uint_16
    data    byte[size]
}

一个Pascal 字符串的替代方案是空终止字符串，其中读取器按字节使用字符串，直到到达字符串结尾符号。Pascal 字符串方法有几个优点：它允许在恒定时间内找出字符串的长度，而不是迭代字符串内容，并且可以通过从内存中切片字节并将字节数组传递给字符串来组成特定于语言的size字符串构造函数。

An alternative to Pascal strings is null-terminated strings, where the reader consumes the string byte-wise until the end-of-string symbol is reached. The Pascal string approach has several advantages: it allows finding out a length of a string in constant time, instead of iterating through string contents, and a language-specific string can be composed by slicing size bytes from memory and passing the byte array to a string constructor.

位打包数据：布尔值、枚举和标志

Bit-Packed Data: Booleans, Enums, and Flags

布尔值可以通过使用单个字节或编码true和falseas1和0值来表示。由于布尔值只有两个值，因此使用整个字节来表示是浪费的，并且开发人员通常将布尔值以八个为一组进行批处理，每个布尔值仅占用一位。我们说每1一位都已设置，每0一位都未设置或为空。

Booleans can be represented either by using a single byte, or encoding true and false as 1 and 0 values. Since a boolean has only two values, using an entire byte for its representation is wasteful, and developers often batch boolean values together in groups of eight, each boolean occupying just one bit. We say that every 1 bit is set and every 0 bit is unset or empty.

枚举，短对于枚举类型，可以表示为整数，通常用于二进制格式和通信协议中。枚举用于表示经常重复的低基数值。例如，我们可以使用枚举对 B 树节点类型进行编码：

Enums, short for enumerated types, can be represented as integers and are often used in binary formats and communication protocols. Enums are used to represent often-repeated low-cardinality values. For example, we can encode a B-Tree node type using an enum:

枚举节点类型{
   根，//0x00h
   内部，//0x01h
   叶 // 0x02h
};

enum NodeType {
   ROOT,     // 0x00h
   INTERNAL, // 0x01h
   LEAF      // 0x02h
};

其他密切相关的概念是标志，一种打包布尔值和枚举的组合。标志可以表示非互斥的命名布尔参数。例如，我们可以使用标志来表示页面是否包含值单元格、值是固定大小还是可变大小以及是否存在与该节点关联的溢出页面。由于每个位都代表一个标志值，因此我们只能使用二次方值作为掩码（因为二进制中的二次方始终有一个设置位；例如 、 等）：23 == 8 == 1000b24 == 16 == 0001 0000b

Another closely related concept is flags, kind of a combination of packed booleans and enums. Flags can represent nonmutually exclusive named boolean parameters. For example, we can use flags to denote whether or not the page holds value cells, whether the values are fixed-size or variable-size, and whether or not there are overflow pages associated with this node. Since every bit represents a flag value, we can only use power-of-two values for masks (since powers of two in binary always have a single set bit; for example, 23 == 8 == 1000b, 24 == 16 == 0001 0000b, etc.):

int IS_LEAF_MASK = 0x01h；// 位#1
int VARIABLE_SIZE_VALUES = 0x02h；// 位#2
int HAS_OVERFLOW_PAGES = 0x04h；// 位#3

int IS_LEAF_MASK         = 0x01h; // bit #1
int VARIABLE_SIZE_VALUES = 0x02h; // bit #2
int HAS_OVERFLOW_PAGES   = 0x04h; // bit #3

只是与打包布尔值一样，可以从打包值中读取和写入标志值使用位掩码和按位运算符。例如，为了设置负责其中一个标志的位，我们可以使用按位OR( |) 和位掩码。我们可以使用bitshift ( <<) 和位索引来代替位掩码。要取消设置该位，我们可以使用按位AND( &) 和按位求反运算符 ( ~)。要测试该位是否n已设置，我们可以将按位的结果AND与0：

Just like packed booleans, flag values can be read and written from the packed value using bitmasks and bitwise operators. For example, in order to set a bit responsible for one of the flags, we can use bitwise OR (|) and a bitmask. Instead of a bitmask, we can use bitshift (<<) and a bit index. To unset the bit, we can use bitwise AND (&) and the bitwise negation operator (~). To test whether or not the bit n is set, we can compare the result of a bitwise AND with 0:

// 设置该位
标志 |= HAS_OVERFLOW_PAGES;
标志 |= (1 << 2);

// 取消该位的设置
标志 &= ~HAS_OVERFLOW_PAGES;
标志 &= ~(1 << 2);

// 测试该位是否已设置
is_set = (flags & HAS_OVERFLOW_PAGES) != 0;
is_set = (标志 & (1 << 2)) != 0;

// Set the bit
flags |= HAS_OVERFLOW_PAGES;
flags |= (1 << 2);

// Unset the bit
flags &= ~HAS_OVERFLOW_PAGES;
flags &= ~(1 << 2);

// Test whether or not the bit is set
is_set = (flags & HAS_OVERFLOW_PAGES) != 0;
is_set = (flags & (1 << 2)) != 0;

神奇数字

Magic Numbers

一通常放置在文件或页眉中的值是一个幻数。通常，它是一个多字节块，包含一个常量值，可用于指示该块代表一个页面、指定其类型或标识其版本。

One of the values often placed in the file or page header is a magic number. Usually, it’s a multibyte block, containing a constant value that can be used to signal that the block represents a page, specify its kind, or identify its version.

幻数经常用于验证和健全性检查[GIAMPAOLO98]。随机偏移处的字节序列与幻数完全匹配是非常不可能的。如果确实匹配，则偏移量很可能是正确的。例如，为了验证页面是否已正确加载和对齐，在写入期间，我们可以将幻数50 41 47 45（十六进制PAGE）放入页眉中。在读取过程中，我们通过将读取标头中的四个字节与预期字节序列进行比较来验证页面。

Magic numbers are often used for validation and sanity checks [GIAMPAOLO98]. It’s very improbable that the byte sequence at a random offset would exactly match the magic number. If it did match, there’s a good chance the offset is correct. For example, to verify that the page is loaded and aligned correctly, during write we can place the magic number 50 41 47 45 (hex for PAGE) into the header. During the read, we validate the page by comparing the four bytes from the read header with the expected byte sequence.

兄弟姐妹链接

Sibling Links

一些实现存储前向和后向链接，指向左右同级页面。这些链接有助于定位相邻节点，而无需上升回父节点。这种方法增加了分割和合并操作的复杂性，因为同级偏移量也必须更新。例如，当非最右边的节点被拆分时，其右兄弟节点的后向指针（之前指向被拆分的节点）必须重新绑定以指向新创建的节点。

Some implementations store forward and backward links, pointing to the left and right sibling pages. These links help to locate neighboring nodes without having to ascend back to the parent. This approach adds some complexity to split and merge operations, as the sibling offsets have to be updated as well. For example, when a non-rightmost node is split, its right sibling’s backward pointer (previously pointing to the node that was split) has to be re-bound to point to the newly created node.

在图4-1中你可以看到，要定位兄弟节点，除非兄弟节点是链接的，否则我们必须引用父节点。此操作可能会一直上升到根，因为直接父级只能帮助寻址其自己的子级。如果我们将同级链接直接存储在标头中，我们可以简单地跟随它们来定位同一级别的上一个或下一个节点。

In Figure 4-1 you can see that to locate a sibling node, unless the siblings are linked, we have to refer to the parent node. This operation might ascend all the way up to the root, since the direct parent can only help to address its own children. If we store sibling links directly in the header, we can simply follow them to locate the previous or next node on the same level.

图 4-1。通过父链接 (a) 与同级链接 (b) 查找同级链接

存储同级链接的缺点之一是它们必须在拆分和合并期间更新。由于更新必须发生在同级节点中，而不是在拆分/合并节点中，因此可能需要额外的锁定。我们讨论兄弟链接如何在“Blink-Trees”中的并发 B-Tree 实现中发挥作用。

One of the downsides of storing sibling links is that they have to be updated during splits and merges. Since updates have to happen in a sibling node, not in a splitting/merging node, it may require additional locking. We discuss how sibling links can be useful in a concurrent B-Tree implementation in “Blink-Trees”.

最右指针

Rightmost Pointers

B 树分隔符键具有严格的不变量：它们用于将树拆分为子树并导航它们，因此指向子页面的指针总是比键多一个。这就是“计数钥匙” +1中提到的出处。

B-Tree separator keys have strict invariants: they’re used to split the tree into subtrees and navigate them, so there is always one more pointer to child pages than there are keys. That’s where the +1 mentioned in “Counting Keys” is coming from.

在“分隔符键”中，我们描述了分隔符键不变量。在许多实现中，节点看起来更像图 4-2中显示的节点：每个分隔符键都有一个子指针，而最后一个指针是单独存储的，因为它不与任何键配对。您可以将此与图 2-10进行比较。

In “Separator Keys”, we described separator key invariants. In many implementations, nodes look more like the ones displayed in Figure 4-2: each separator key has a child pointer, while the last pointer is stored separately, since it’s not paired with any key. You can compare this to Figure 2-10.

图 4-2。最右指针

这额外的指针可以存储在标头中，例如，它是在SQLite中实现的。

This extra pointer can be stored in the header as, for example, it is implemented in SQLite.

如果最右边的子单元被拆分并且新单元格附加到其父单元，则必须重新分配最右边的子单元指针。如图4-3所示，分裂后，附加到父级的单元格（以灰色显示）保存提升的键并指向分裂节点。分配指向新节点的指针而不是先前最右边的指针。SQLite 中描述并实现了类似的方法。¹

If the rightmost child is split and the new cell is appended to its parent, the rightmost child pointer has to be reassigned. As shown in Figure 4-3, after the split, the cell appended to the parent (shown in gray) holds the promoted key and points to the split node. The pointer to the new node is assigned instead of the previous rightmost pointer. A similar approach is described and implemented in SQLite.¹

图 4-3。节点分裂期间最右指针更新。升级后的密钥显示为灰色。

节点高调

Node High Keys

我们可以采取稍微不同的方法，将最右边的指针与节点高键一起存储在单元格中。高键表示当前节点下的子树中可以存在的最高可能键。这种方法的使用者是PostgreSQL 被称为B ^link -Trees（有关此方法的并发影响，请参阅“Blink-Trees”）。

We can take a slightly different approach and store the rightmost pointer in the cell along with the node high key. The high key represents the highest possible key that can be present in the subtree under the current node. This approach is used by PostgreSQL and is called B^link-Trees (for concurrency implications of this approach, see “Blink-Trees”).

B 树有N键（用 表示）和指针（用 表示）。在每个子树中，键以 为界。是隐式的并且不存在于节点中。KiN + 1PiKi-1 ≤ Ks < KiK0 = -∞

B-Trees have N keys (denoted with Ki) and N + 1 pointers (denoted with Pi). In each subtree, keys are bounded by Ki-1 ≤ Ks < Ki. The K0 = -∞ is implicit and is not present in the node.

B ^link - 树为每个节点添加一个键。它指定可以存储在指针指向的子树中的键的上限，因此也是可以存储在当前子树中的值的上限。两种方法如图 4-4所示：(a) 显示没有高密钥的节点，(b) 显示具有高密钥的节点。KN+1PN

B^link-Trees add a KN+1 key to each node. It specifies an upper bound of keys that can be stored in the subtree to which the pointer PN points, and therefore is an upper bound of values that can be stored in the current subtree. Both approaches are shown in Figure 4-4: (a) shows a node without a high key, and (b) shows a node with a high key.

图 4-4。不带 (a) 和带 (b) 高键的 B 树

在这种情况下，指针可以成对存储，并且每个单元格可以有一个相应的指针，这可能会简化最右边的指针处理，因为没有那么多的边缘情况需要考虑。

In this case, pointers can be stored pairwise, and each cell can have a corresponding pointer, which might simplify rightmost pointer handling as there are not as many edge cases to consider.

在图 4-5中，您可以看到两种方法的示意性页面结构，以及在这些情况下如何以不同方式分割搜索空间：在第一种情况下向上到，在第二种情况下 +∞向上到上限。K3

In Figure 4-5, you can see schematic page structure for both approaches and how the search space is split differently for these cases: going up to +∞ in the first case, and up to the upper bound of K3 in the second.

图 4-5。使用 +∞ 作为虚拟键 (a) 与存储高键 (b)

溢出页

Overflow Pages

节点大小树扇出值是固定的，不会动态变化。提出一个普遍最佳的值也很困难：如果树中存在可变大小的值并且它们足够大，则只有其中少数可以适合页面。如果值很小，我们最终会浪费保留空间。

Node size and tree fanout values are fixed and do not change dynamically. It would also be difficult to come up with a value that would be universally optimal: if variable-size values are present in the tree and they are large enough, only a few of them can fit into the page. If the values are tiny, we end up wasting the reserved space.

B 树算法指定每个节点保留特定数量的项目。由于某些值具有不同的大小，因此根据 B-Tree 算法，我们最终可能会遇到这样的情况：节点尚未满，但保存该节点的固定大小页面上没有更多可用空间。调整页面大小需要将已写入的数据复制到新区域，这通常是不切实际的。然而，我们仍然需要找到一种方法来增加或扩展页面大小。

The B-Tree algorithm specifies that every node keeps a specific number of items. Since some values have different sizes, we may end up in a situation where, according to the B-Tree algorithm, the node is not full yet, but there’s no more free space on the fixed-size page that holds this node. Resizing the page requires copying already written data to the new region and is often impractical. However, we still need to find a way to increase or extend the page size.

为了实现可变大小的节点而不将数据复制到新的连续区域，我们可以从多个链接页面构建节点。例如，默认页面大小为 4 K，插入几个值后，其数据大小已增长超过 4 K。节点不允许任意大小，而是允许以 4 K 增量增长，因此我们分配 4 K 扩展页面并链接到原始页面。这些链接的页面扩展称为溢出页面。为了清楚起见，我们称原始页面本节范围内的主页。

To implement variable-size nodes without copying data to the new contiguous region, we can build nodes from multiple linked pages. For example, the default page size is 4 K, and after inserting a few values, its data size has grown over 4 K. Instead of allowing arbitrary sizes, nodes are allowed to grow in 4 K increments, so we allocate a 4 K extension page and link it from the original one. These linked page extensions are called overflow pages. For clarity, we call the original page the primary page in the scope of this section.

大多数 B-Tree 实现仅允许直接在 B-Tree 节点中存储最多固定数量的有效负载字节，并将其余字节溢出到溢出页。该值是通过将节点大小除以扇出来计算的。使用这种方法，我们不会最终遇到页面没有可用空间的情况，因为它总是至少有max_payload_size字节。为了有关 SQLite 中溢出页面的更多信息，请参阅SQLite 源代码存储库；还可以查看MySQL InnoDB 文档。

Most B-Tree implementations allow storing only up to a fixed number of payload bytes in the B-Tree node directly and spilling the rest to the overflow page. This value is calculated by dividing the node size by fanout. Using this approach, we cannot end up in a situation where the page has no free space, as it will always have at least max_payload_size bytes. For more information on overflow pages in SQLite, see the SQLite source code repository; also check out the MySQL InnoDB documentation.

当插入的有效负载大于 时max_payload_size，将检查该节点是否已经具有任何关联的溢出页面。如果溢出页面已经存在并且有足够的可用空间，则有效负载中的额外字节会溢出到那里。否则，分配新的溢出页。

When the inserted payload is larger than max_payload_size, the node is checked for whether or not it already has any associated overflow pages. If an overflow page already exists and has enough space available, extra bytes from the payload are spilled there. Otherwise, a new overflow page is allocated.

在图 4-6中，您可以看到一个主页面和一个溢出页面，其中的记录从主页面指向溢出页面，其负载继续在溢出页面上。

In Figure 4-6, you can see a primary page and an overflow page with records pointing from the primary page to the overflow one, where their payload continues.

图 4-6。溢出页面

溢出页面需要一些额外的簿记，因为它们可能会像主页面一样碎片化，并且我们必须能够回收该空间来写入新数据，或者在不再需要时丢弃溢出页面。

Overflow pages require some extra bookkeeping, since they may get fragmented as well as primary pages, and we have to be able to reclaim this space to write new data, or discard the overflow page if it’s not needed anymore.

当第一个溢出页被分配时，它的页ID被存储在主页的页头中。如果单个溢出页不够，则通过将下一个溢出页 ID 存储在前一个溢出页的页眉中，将多个溢出页链接在一起。可能需要遍历几个页面才能找到给定有效负载的溢出部分。

When the first overflow page is allocated, its page ID is stored in the header of the primary page. If a single overflow page is not enough, multiple overflow pages are linked together by storing the next overflow page ID in the previous one’s header. Several pages may have to be traversed to locate the overflow part for the given payload.

由于键通常具有高基数，因此存储键的一部分是有意义的，因为大多数比较可以在驻留在主页中的修剪后的键部分上进行。

Since keys usually have high cardinality, storing a portion of a key makes sense, as most of the comparisons can be made on the trimmed key part that resides in the primary page.

对于数据记录，我们必须找到其溢出部分以将其返回给用户。然而，这并不重要，因为这是一个不频繁的操作。如果所有数据记录都过大，则值得考虑专门针对大值进行 Blob 存储。

For data records, we have to locate their overflow parts to return them to the user. However, this doesn’t matter much, since it’s an infrequent operation. If all data records are oversize, it is worth considering specialized blob storage for large values.

使用间接指针的二分查找

Binary Search with Indirection Pointers

细胞B-Tree 页面中的元素按插入顺序存储，只有单元格偏移量保留逻辑元素顺序。要通过页面单元格执行二分搜索，我们选择中间的单元格偏移量，跟随其指针定位该单元格，将该单元格中的键与搜索到的键进行比较，以决定是否应该继续向左或向右搜索，并递归地继续此过程，直到找到查找到的元素或插入点，如图4-7所示。

Cells in the B-Tree page are stored in the insertion order, and only cell offsets preserve the logical element order. To perform binary search through page cells, we pick the middle cell offset, follow its pointer to locate the cell, compare the key from this cell with the searched key to decide whether the search should continue left or right, and continue this process recursively until the searched element or the insertion point is found, as shown in Figure 4-7.

图 4-7。使用间接指针进行二分查找。搜索到的元素显示为灰色。虚线箭头表示通过单元格指针进行二分搜索。实线表示跟随单元格指针的访问，这是将单元格值与搜索到的键进行比较所必需的。

面包屑

Breadcrumbs

反而通过存储和维护父节点指针，可以跟踪在到目标叶节点的路径上遍历的节点，并在插入期间级联拆分或删除期间合并的情况下以相反的顺序跟踪父节点链。

Instead of storing and maintaining parent node pointers, it is possible to keep track of nodes traversed on the path to the target leaf node, and follow the chain of parent nodes in reverse order in case of cascading splits during inserts, or merges during deletes.

在可能导致B-Tree结构改变的操作（插入或删除）中，我们首先从根到叶遍历树，找到目标节点和插入点。由于我们并不总是预先知道该操作是否会导致拆分或合并（至少在找到目标叶节点之前不会），因此我们必须收集面包屑。

During operations that may result in structural changes of the B-Tree (insert or delete), we first traverse the tree from the root to the leaf to find the target node and the insertion point. Since we do not always know up front whether or not the operation will result in a split or merge (at least not until the target leaf node is located), we have to collect breadcrumbs.

面包屑包含对从根开始的节点的引用，并用于在传播拆分或合并时反向回溯它们。最自然的数据结构是堆栈。例如，PostgreSQL 将面包屑存储在堆栈中，内部引用为 BTStack。²

Breadcrumbs contain references to the nodes followed from the root and are used to backtrack them in reverse when propagating splits or merges. The most natural data structure for this is a stack. For example, PostgreSQL stores breadcrumbs in a stack, internally referenced as BTStack.²

如果节点被拆分或合并，则面包屑可用于查找拉到父级的键的插入点，并在必要时返回树以将结构更改传播到更高级别的节点。该堆栈保存在内存中。

If the node is split or merged, breadcrumbs can be used to find insertion points for the keys pulled to the parent and to walk back up the tree to propagate structural changes to the higher-level nodes, if necessary. This stack is maintained in memory.

图 4-8显示了根到叶遍历的示例，收集包含指向已访问节点和单元索引的指针的面包屑。如果目标叶节点被拆分，则弹出堆栈顶部的项目以找到其直接父节点。如果父节点有足够的空间，则会在面包屑中的单元索引处向其追加一个新单元（假设该索引仍然有效）。否则，父节点也会被分裂。这个过程递归地继续下去，直到堆栈为空并且我们到达了根，或者级别上没有分裂。

Figure 4-8 shows an example of root-to-leaf traversal, collecting breadcrumbs containing pointers to the visited nodes and cell indices. If the target leaf node is split, the item on top of the stack is popped to locate its immediate parent. If the parent node has enough space, a new cell is appended to it at the cell index from the breadcrumb (assuming the index is still valid). Otherwise, the parent node is split as well. This process continues recursively until either the stack is empty and we have reached the root, or there was no split on the level.

图 4-8。查找期间收集的面包屑，包含遍历的节点和单元索引。虚线表示到访问节点的逻辑链接。面包屑表中的数字表示后续子指针的索引。

批量装载

Bulk Loading

如果我们已经预先排序了数据并想要批量加载它，或者必须重建树（例如，为了碎片整理），我们可以进一步采用仅右附加的想法。由于创建树所需的数据已经排序，因此在批量加载期间，我们只需将项目附加到树中最右侧的位置即可。

If we have presorted data and want to bulk load it, or have to rebuild the tree (for example, for defragmentation), we can take the idea with right-only appends even further. Since the data required for tree creation is already sorted, during bulk loading we only need to append the items at the rightmost location in the tree.

在这种情况下，我们可以完全避免拆分和合并，而是从下往上构建树，逐级写出，或者一旦有足够的指向已写入的较低级别节点的指针，就写出较高级别的节点。

In this case, we can avoid splits and merges altogether and compose the tree from the bottom up, writing it out level by level, or writing out higher-level nodes as soon as we have enough pointers to already written lower-level nodes.

实现批量加载的一种方法是在叶级逐页写入预排序数据（而不是插入单个元素）。写入叶页后，我们将其第一个键传播到父级，并使用正常算法来构建更高的 B 树级别[RAMAKRISHNAN03]。由于附加键是按排序顺序给出的，因此这种情况下的所有拆分都发生在最右边的节点上。

One approach for implementing bulk loading is to write presorted data on the leaf level page-wise (rather then inserting individual elements). After the leaf page is written, we propagate its first key to the parent and use a normal algorithm for building higher B-Tree levels [RAMAKRISHNAN03]. Since appended keys are given in the sorted order, all splits in this case occur on the rightmost node.

由于 B 树总是从底部（叶）级别开始构建，因此可以在组成任何更高级别的节点之前写出完整的叶级别。这允许在构建更高级别时拥有所有子指针。这种方法的主要好处是，我们不必在磁盘上执行任何拆分或合并，同时只需保留树的最小部分（即当前填充叶节点的所有父节点）。建造时的记忆。

Since B-Trees are always built starting from the bottom (leaf) level, the complete leaf level can be written out before any higher-level nodes are composed. This allows having all child pointers at hand by the time the higher levels are constructed. The main benefits of this approach are that we do not have to perform any splits or merges on disk and, at the same time, have to keep only a minimal part of the tree (i.e., all parents of the currently filling leaf node) in memory for the time of construction.

不可变 B 树可以用相同的方式创建，但与可变 B 树不同，它们不需要后续修改的空间开销，因为树上的所有操作都是最终的。所有页面都可以完全填满，从而提高占用率并获得更好的性能。

Immutable B-Trees can be created in the same manner but, unlike mutable B-Trees, they require no space overhead for subsequent modifications, since all operations on a tree are final. All pages can be completely filled up, improving occupancy and resulting into better performance.

更新和删除导致的碎片

Fragmentation Caused by Updates and Deletes

让我们考虑一下在这种情况下，页面会进入具有不可寻址数据并且必须进行压缩的状态。在叶级别，删除仅删除标题中的单元格偏移量，使单元格本身保持完整。完成此操作后，该单元格将不再可寻址，其内容将不会出现在查询结果中，并且无需将其无效或移动相邻单元格。

Let’s consider under which circumstances pages get into the state where they have nonaddressable data and have to be compacted. On the leaf level, deletes only remove cell offsets from the header, leaving the cell itself intact. After this is done, the cell is not addressable anymore, its contents will not appear in the query results, and nullifying it or moving neighboring cells is not necessary.

当页面被分割时，仅修剪偏移量，并且由于页面的其余部分不可寻址，因此偏移量被截断的单元格不可访问，因此每当新数据到达时它们将被覆盖，或者在真空处理时被垃圾收集开始。

When the page is split, only offsets are trimmed and, since the rest of the page is not addressable, cells whose offsets were truncated are not reachable, so they will be overwritten whenever the new data arrives, or garbage-collected when the vacuum process kicks in.

由于删除仅丢弃单元偏移量，并且不会重新定位剩余单元或物理删除目标单元以占用释放的空间，因此释放的字节可能最终分散在整个页面上。在这种情况下，我们说页面有碎片，需要进行碎片整理。

Since deletes only discard cell offsets and do not relocate remaining cells or physically remove the target cells to occupy the freed space, freed bytes might end up scattered across the page. In this case, we say that the page is fragmented and requires defragmentation.

为了进行写入，我们通常需要一个连续的空闲字节块来容纳单元。为了将释放的片段重新组合在一起并解决这种情况，我们必须重写页面。

To make a write, we often need a contiguous block of free bytes where the cell fits. To put the freed fragments back together and fix this situation, we have to rewrite the page.

插入操作将元组保留在其插入顺序中。这不会产生那么大的影响，但是自然排序的元组可以帮助在顺序读取期间进行缓存预取。

Insert operations leave tuples in their insertion order. This does not have as significant an impact, but having naturally sorted tuples can help with cache prefetch during sequential reads.

更新主要适用于叶级别：内部页面键用于引导导航并且仅定义子树边界。此外，更新是在每个键的基础上执行的，除了创建溢出页面之外，通常不会导致树中的结构变化。然而，在叶级别，更新操作不会更改单元顺序并尝试避免页面重写。这意味着单元的多个版本（其中只有一个是可寻址的）最终可能会被存储。

Updates are mostly applicable to the leaf level: internal page keys are used for guided navigation and only define subtree boundaries. Additionally, updates are performed on a per-key basis, and generally do not result in structural changes in the tree, apart from the creation of overflow pages. On the leaf level, however, update operations do not change cell order and attempt to avoid page rewrite. This means that multiple versions of the cell, only one of which is addressable, may end up being stored.

页面碎片整理

Page Defragmentation

这负责空间回收和页面重写的过程称为压缩、清理或简称维护。如果页面没有足够的可用物理空间（以避免创建不必要的溢出页面），则可以在写入时同步完成页面重写，但压缩通常被称为遍历页面、执行垃圾收集和重写的独特的异步过程他们的内容。

The process that takes care of space reclamation and page rewrites is called compaction, vacuum, or just maintenance. Page rewrites can be done synchronously on write if the page does not have enough free physical space (to avoid creating unnecessary overflow pages), but compaction is mostly referred to as a distinct, asynchronous process of walking through pages, performing garbage collection, and rewriting their contents.

此过程回收死单元占据的空间，并按单元的逻辑顺序重写单元。当页面被重写时，它们也可能被重新定位到文件中的新位置。未使用的内存页面变得可用并返回到页面缓存。ID新可用的磁盘页面被添加到空闲页面列表（有时称为空闲列表³）。必须保留此信息，以便在节点崩溃和重新启动时幸存下来，并确保可用空间不会丢失或泄漏。

This process reclaims the space occupied by dead cells, and rewrites cells in their logical order. When pages are rewritten, they may also get relocated to new positions in the file. Unused in-memory pages become available and are returned to the page cache. IDs of the newly available on-disk pages are added to the free page list (sometimes called a freelist³). This information has to be persisted to survive node crashes and restarts, and to make sure free space is not lost or leaked.

日志语义

Log Semantics

这预写日志是仅追加的，其写入的内容是不可变的，因此对日志的所有写入都是顺序的。由于 WAL 是不可变的、仅追加的数据结构，因此读取器可以安全地访问其内容，直到最新的写入阈值，同时写入器继续将数据追加到日志尾部。

The write-ahead log is append-only and its written contents are immutable, so all writes to the log are sequential. Since the WAL is an immutable, append-only data structure, readers can safely access its contents up to the latest write threshold while the writer continues appending data to the log tail.

WAL 由日志记录组成。每张唱片都有其独特的、单调的增加日志序列号(LSN)。通常，LSN 由内部计数器或时间戳表示。由于日志记录不一定占用整个磁盘块，因此它们的内容被缓存在 日志缓冲区并在强制操作中刷新到磁盘上。当日志缓冲区填满时会发生强制，并且可以由事务管理器或页面缓存请求。所有日志记录都必须按 LSN 顺序刷新到磁盘上。

The WAL consists of log records. Every record has a unique, monotonically increasing log sequence number (LSN). Usually, the LSN is represented by an internal counter or a timestamp. Since log records do not necessarily occupy an entire disk block, their contents are cached in the log buffer and are flushed on disk in a force operation. Forces happen as the log buffers fill up, and can be requested by the transaction manager or a page cache. All log records have to be flushed on disk in LSN order.

除了单独的操作记录外，WAL 还保存指示事务完成的记录。在日志强制达到其提交记录的 LSN 之前，不能将事务视为已提交。

Besides individual operation records, the WAL holds records indicating transaction completion. A transaction can’t be considered committed until the log is forced up to the LSN of its commit record.

为了确保系统在回滚或恢复期间崩溃后能够继续正常运行，一些系统在撤消期间使用补偿日志记录（CLR）并将其存储在日志中。

To make sure the system can continue functioning correctly after a crash during rollback or recovery, some systems use compensation log records (CLR) during undo and store them in the log.

WAL 通常通过接口与主存储结构耦合，该接口允许 每当到达检查点时就修剪它。日志记录是数据库最关键的正确性方面之一，要正确执行这一点有些棘手：即使日志修剪和确保数据已进入主存储结构之间最轻微的分歧也可能会导致数据丢失。

The WAL is usually coupled with a primary storage structure by the interface that allows trimming it whenever a checkpoint is reached. Logging is one of the most critical correctness aspects of the database, which is somewhat tricky to get right: even the slightest disagreements between log trimming and ensuring that the data has made it to the primary storage structure may cause data loss.

检查点是日志了解达到特定标记的日志记录已完全持久并且不再需要的一种方式，这显着减少了数据库启动期间所需的工作量。A强制将所有脏页刷新到磁盘上的过程通常称为同步检查点，因为它完全同步主存储结构。

Checkpoints are a way for a log to know that log records up to a certain mark are fully persisted and aren’t required anymore, which significantly reduces the amount of work required during the database startup. A process that forces all dirty pages to be flushed on disk is generally called a sync checkpoint, as it fully synchronizes the primary storage structure.

刷新磁盘上的全部内容是相当不切实际的，并且需要暂停所有正在运行的操作，直到检查点完成，因此大多数数据库系统都实现模糊检查点。在这种情况下，存储last_checkpoint在日志头中的指针包含有关最后一个成功检查点的信息。模糊检查点以指定其开始的特殊begin_checkpoint日志记录开始，以日志记录结束end_checkpoint，其中包含有关脏页的信息以及事务表的内容。直到该记录指定的所有页面都被刷新为止，才认为检查点不完整。页面被异步刷新，一旦完成，last_checkpoint记录将使用记录的 LSN 进行更新begin_checkpoint，并且在发生崩溃时，恢复过程将从那里开始[MOHAN92]。

Flushing the entire contents on disk is rather impractical and would require pausing all running operations until the checkpoint is done, so most database systems implement fuzzy checkpoints. In this case, the last_checkpoint pointer stored in the log header contains the information about the last successful checkpoint. A fuzzy checkpoint begins with a special begin_checkpoint log record specifying its start, and ends with end_checkpoint log record, containing information about the dirty pages, and the contents of a transaction table. Until all the pages specified by this record are flushed, the checkpoint is considered to be incomplete. Pages are flushed asynchronously and, once this is done, the last_checkpoint record is updated with the LSN of the begin_checkpoint record and, in case of a crash, the recovery process will start from there [MOHAN92].

操作与数据日志

Operation Versus Data Log

一些数据库系统，例如 System R [CHAMBERLIN81]，使用影子分页：一种写入时复制技术，确保数据持久性和事务原子性。新内容被放置到新的未发布的影子页面中，并通过指针翻转（从旧页面到包含更新内容的页面）使其可见。

Some database systems, for example System R [CHAMBERLIN81], use shadow paging: a copy-on-write technique ensuring data durability and transaction atomicity. New contents are placed into the new unpublished shadow page and made visible with a pointer flip, from the old page to the one holding updated contents.

任何状态变化都可以由前像和后像或相应的重做和撤消操作来表示。正在申请对前像的重做操作会产生后像。类似地，对后像应用撤消操作会产生前像。

Any state change can be represented by a before-image and an after-image or by corresponding redo and undo operations. Applying a redo operation to a before-image produces an after-image. Similarly, applying an undo operation to an after-image produces a before-image.

我们可以使用物理日志（存储完整的页面状态或对其进行按字节更改）或逻辑日志（存储必须针对当前状态执行的操作）将记录或页面从一种状态移动到另一种状态时间上向后和向前。跟踪物理和逻辑日志记录可应用的页面的确切状态非常重要。

We can use a physical log (that stores complete page state or byte-wise changes to it) or a logical log (that stores operations that have to be performed against the current state) to move records or pages from one state to the other, both backward and forward in time. It is important to track the exact state of the pages that physical and logical log records can be applied to.

物理日志记录图像前后的情况，需要记录受操作影响的整个页面。逻辑日志指定必须对页面应用哪些操作，例如"insert a data record X for key Y"，以及相应的撤消操作，例如"remove the value associated with Y"。

Physical logging records before and after images, requiring entire pages affected by the operation to be logged. A logical log specifies which operations have to be applied to the page, such as "insert a data record X for key Y", and a corresponding undo operation, such as "remove the value associated with Y".

在实践中，许多数据库系统结合使用这两种方法，使用逻辑日志记录来执行撤消（为了并发性和性能），使用物理日志记录来执行重做（为了提高恢复时间）[MOHAN92 ]。

In practice, many database systems use a combination of these two approaches, using logical logging to perform an undo (for concurrency and performance) and physical logging to perform a redo (to improve recovery time) [MOHAN92].

盗窃和强制政策

Steal and Force Policies

到为了确定何时必须将内存中所做的更改刷新到磁盘上，数据库管理系统定义窃取/不窃取和强制/不强制策略。这些策略主要适用于页面缓存，但最好在恢复上下文中讨论它们，因为它们对于可以与它们结合使用的恢复方法具有重大影响。

To determine when the changes made in memory have to be flushed on disk, database management systems define steal/no-steal and force/no-force policies. These policies are mostly applicable to the page cache, but they’re better discussed in the context of recovery, since they have a significant impact on which recovery approaches can be used in combination with them.

即使在事务提交之前也允许刷新事务修改的页面的恢复方法称为窃取策略。无窃取策略不允许刷新磁盘上任何未提交的事务内容。这里窃取脏页意味着将其内存内容刷新到磁盘并从磁盘加载不同的页面来代替它。

A recovery method that allows flushing a page modified by the transaction even before the transaction has committed is called a steal policy. A no-steal policy does not allow flushing any uncommitted transaction contents on disk. To steal a dirty page here means flushing its in-memory contents to disk and loading a different page from disk in its place.

强制策略要求在事务提交之前将事务修改的所有页面刷新到磁盘上。另一方面，无强制策略允许事务提交，即使在此事务期间修改的某些页面尚未刷新到磁盘上也是如此。这里强制使用脏页意味着在提交之前将其刷新到磁盘上。

A force policy requires all pages modified by the transactions to be flushed on disk before the transaction commits. On the other hand, a no-force policy allows a transaction to commit even if some pages modified during this transaction were not yet flushed on disk. To force a dirty page here means to flush it on disk before the commit.

偷理解和强制策略很重要，因为它们对事务撤消和重做有影响。撤消将更新回滚到已提交事务的强制页面，而重做则应用磁盘上已提交事务执行的更改。

Steal and force policies are important to understand, since they have implications for transaction undo and redo. Undo rolls back updates to forced pages for committed transactions, while redo applies changes performed by committed transactions on disk.

使用无窃取策略允许仅使用重做条目来实现恢复：旧副本包含在磁盘上的页面中，修改存储在日志中[WEIKUM01]。使用no-force，我们可以通过推迟页面的多次更新来缓冲它们。由于当时页面内容必须缓存在内存中，因此可能需要更大的页面缓存。

Using the no-steal policy allows implementing recovery using only redo entries: old copy is contained in the page on disk and modification is stored in the log [WEIKUM01]. With no-force, we potentially can buffer several updates to pages by deferring them. Since page contents have to be cached in memory for that time, a larger page cache may be needed.

当使用强制策略时，崩溃恢复不需要任何额外的工作来重建已提交事务的结果，因为这些事务修改的页面已经被刷新。使用此方法的一个主要缺点是，由于必要的 I/O，事务需要更长的时间才能提交。

When the force policy is used, crash recovery doesn’t need any additional work to reconstruct the results of committed transactions, since pages modified by these transactions are already flushed. A major drawback of using this approach is that transactions take longer to commit due to the necessary I/O.

更一般地说，在事务提交之前，我们需要有足够的信息来撤消其结果。如果事务触及的任何页面被刷新，我们需要在日志中保留撤消信息，直到它提交才能回滚。否则，我们必须在日志中保留重做记录，直到提交为止。在这两种情况下，在撤消或重做记录写入日志文件之前，事务无法提交。

More generally, until the transaction commits, we need to have enough information to undo its results. If any pages touched by the transaction are flushed, we need to keep undo information in the log until it commits to be able to roll it back. Otherwise, we have to keep redo records in the log until it commits. In both cases, transaction cannot commit until either undo or redo records are written to the logfile.

白羊座

ARIES

白羊座是一种窃取/无强制恢复算法。它使用物理重做来提高恢复期间的性能（因为可以更快地安装更改），并使用逻辑撤消来提高正常操作期间的并发性（因为逻辑撤消操作可以独立应用于页面）。它使用WAL记录来实现恢复期间的重复历史，在撤消未提交的事务之前完全重建数据库状态，并在撤消期间创建补偿日志记录[MOHAN92]。

ARIES is a steal/no-force recovery algorithm. It uses physical redo to improve performance during recovery (since changes can be installed quicker) and logical undo to improve concurrency during normal operation (since logical undo operations can be applied to pages independently). It uses WAL records to implement repeating history during recovery, to completely reconstruct the database state before undoing uncommitted transactions, and creates compensation log records during undo [MOHAN92].

当数据库系统崩溃后重新启动时，恢复分三个阶段进行：

When the database system restarts after the crash, recovery proceeds in three phases:

1. 分析阶段识别页面缓存中的脏页以及崩溃时正在进行的事务。有关脏页的信息用于识别重做阶段的起点。在撤消阶段使用正在进行的事务列表来回滚未完成的事务。

2. The analysis phase identifies dirty pages in the page cache and transactions that were in progress at the time of a crash. Information about dirty pages is used to identify the starting point for the redo phase. A list of in-progress transactions is used during the undo phase to roll back incomplete transactions.

3. 重做阶段重复历史记录直至崩溃点，并将数据库恢复到之前的状态。此阶段针对不完整的事务以及已提交但其内容未刷新到持久存储的事务。

4. The redo phase repeats the history up to the point of a crash and restores the database to the previous state. This phase is done for incomplete transactions as well as ones that were committed but whose contents weren’t flushed to persistent storage.

5. 撤消阶段回滚所有未完成的事务并将数据库恢复到最后的一致状态。所有操作均按时间倒序回滚。如果数据库在恢复过程中再次崩溃，撤消事务的操作也会被记录下来以避免重复。

6. The undo phase rolls back all incomplete transactions and restores the database to the last consistent state. All operations are rolled back in reverse chronological order. In case the database crashes again during recovery, operations that undo transactions are logged as well to avoid repeating them.

ARIES 使用 LSN 来识别日志记录，跟踪脏页表中运行事务修改的页面，并使用物理重做、逻辑撤消和模糊检查点。尽管描述该系统的论文于 1992 年发布，但大多数概念、方法和范例在今天的事务处理和恢复中仍然相关。

ARIES uses LSNs for identifying log records, tracks pages modified by running transactions in the dirty page table, and uses physical redo, logical undo, and fuzzy checkpointing. Even though the paper describing this system was released in 1992, most concepts, approaches, and paradigms are still relevant in transaction processing and recovery today.

可串行化

Serializability

交易由针对数据库状态执行的读取和写入操作以及业务逻辑（应用于读取内容的转换）组成。A 调度是从数据库系统角度执行一组事务所需的操作列表（即，仅与数据库状态交互的操作，例如读、写、提交或中止操作），因为假设所有其他操作无副作用（换句话说，对数据库状态没有影响）[MOLINA08]。

Transactions consist of read and write operations executed against the database state, and business logic (transformations, applied to the read contents). A schedule is a list of operations required to execute a set of transactions from the database-system perspective (i.e., only ones that interact with the database state, such as read, write, commit, or abort operations), since all other operations are assumed to be side-effect free (in other words, have no impact on the database state) [MOLINA08].

A如果计划包含其中执行的每个事务的所有操作，则计划是完整的。正确的计划在逻辑上等同于原始操作列表，但它们的部分可以并行执行或出于优化目的重新排序，只要这不违反 ACID 属性和单个事务结果的正确性[WEIKUM01]。

A schedule is complete if contains all operations from every transaction executed in it. Correct schedules are logical equivalents to the original lists of operations, but their parts can be executed in parallel or get reordered for optimization purposes, as long as this does not violate ACID properties and the correctness of the results of individual transactions [WEIKUM01].

A当调度中的事务完全独立执行并且没有任何交错时，调度被称为串行：每个先前的事务在下一个事务开始之前完全执行。与多个多步骤事务之间所有可能的交错相比，串行执行很容易推理。然而，总是一个接一个地执行事务会显着限制系统吞吐量并损害性能。

A schedule is said to be serial when transactions in it are executed completely independently and without any interleaving: every preceding transaction is fully executed before the next one starts. Serial execution is easy to reason about, as contrasted with all possible interleavings between several multistep transactions. However, always executing transactions one after another would significantly limit the system throughput and hurt performance.

我们需要找到一种方法来并发执行事务操作，同时保持串行调度的正确性和简单性。我们可以通过可序列化的调度来实现这一点。如果调度相当于同一组事务上的某个完整串行调度，则该调度是可序列化的。换句话说，它产生的结果与我们按某种顺序依次执行一组事务相同。图 5-4显示了三个并发事务，以及可能的执行历史（3! = 6可能性，以每种可能的顺序）。

We need to find a way to execute transaction operations concurrently, while maintaining the correctness and simplicity of a serial schedule. We can achieve this with serializable schedules. A schedule is serializable if it is equivalent to some complete serial schedule over the same set of transactions. In other words, it produces the same result as if we executed a set of transactions one after another in some order. Figure 5-4 shows three concurrent transactions, and possible execution histories (3! = 6 possibilities, in every possible order).

图 5-4。并发事务及其可能的顺序执行历史

事务隔离

Transaction Isolation

交易性数据库系统允许不同的隔离级别。隔离级别指定事务的某些部分如何以及何时可以并且应该对其他事务可见。换句话说，隔离级别描述了事务与其他并发执行的事务隔离的程度，以及执行过程中可能遇到哪些类型的异常。

Transactional database systems allow different isolation levels. An isolation level specifies how and when parts of the transaction can and should become visible to other transactions. In other words, isolation levels describe the degree to which transactions are isolated from other concurrently executing transactions, and what kinds of anomalies can be encountered during execution.

实现隔离是有代价的：为了防止不完整或临时写入跨越事务边界传播，我们需要额外的协调和同步，这会对性能产生负面影响。

Achieving isolation comes at a cost: to prevent incomplete or temporary writes from propagating over transaction boundaries, we need additional coordination and synchronization, which negatively impacts the performance.

读写异常

Read and Write Anomalies

这SQL 标准[MELTON06]引用并描述了并发事务执行期间可能发生的读取异常：脏读、不可重复读和幻读。

The SQL standard [MELTON06] refers to and describes read anomalies that can occur during execution of concurrent transactions: dirty, nonrepeatable, and phantom reads.

脏读是事务可以从其他事务读取未提交的更改的情况。例如，事务使用地址字段的新值更新用户记录，并且事务在提交之前读取更新的地址。事务中止并回滚其执行结果。然而，已经能够读取这个值，因此它访问了从未提交的值。T1T2T1T1T2

A dirty read is a situation in which a transaction can read uncommitted changes from other transactions. For example, transaction T1 updates a user record with a new value for the address field, and transaction T2 reads the updated address before T1 commits. Transaction T1 aborts and rolls back its execution results. However, T2 has already been able to read this value, so it has accessed the value that has never been committed.

不可重复读取（有时称为模糊读取）是指事务两次查询同一行并得到不同结果的情况。例如，即使事务读取一行，然后事务修改它并提交此更改，也可能发生这种情况。如果在执行完成之前再次请求同一行，则结果将与上次运行不同。T1T2T1

A nonrepeatable read (sometimes called a fuzzy read) is a situation in which a transaction queries the same row twice and gets different results. For example, this can happen even if transaction T1 reads a row, then transaction T2 modifies it and commits this change. If T1 requests the same row again before finishing its execution, the result will differ from the previous run.

如果如果我们在事务期间使用范围读取（即，读取的不是单个数据记录，而是一系列记录），我们可能会看到幻影记录。幻读是指事务两次查询同一行集并收到不同的结果。它类似于不可重复读取，但适用于范围查询。

If we use range reads during the transaction (i.e., read not a single data record, but a range of records), we might see phantom records. A phantom read is when a transaction queries the same set of rows twice and receives different results. It is similar to a nonrepeatable read, but holds for range queries.

那里也是具有类似语义的写异常：丢失更新、脏写和写倾斜。

There are also write anomalies with similar semantics: lost update, dirty write, and write skew.

发生更新丢失当交易和都尝试更新 的值时。并读取 的值。更新和提交，然后更新并提交。由于事务不知道彼此的存在，如果都允许提交，则 的结果将被 的结果覆盖，并且 from 的更新将丢失。T1T2VT1T2VT1VT2VT1T2T1

A lost update occurs when transactions T1 and T2 both attempt to update the value of V. T1 and T2 read the value of V. T1 updates V and commts, and T2 updates V after that and commits as well. Since the transactions are not aware about each other’s existence, if both of them are allowed to commit, the results of T1 will be overwritten by the results of T2, and the update from T1 will be lost.

脏写是其中一个事务获取未提交的值（即脏读）、修改它并保存它的情况。换句话说，当事务结果基于从未提交的值时。

A dirty write is a situation in which one of the transactions takes an uncommitted value (i.e., dirty read), modifies it, and saves it. In other words, when transaction results are based on the values that have never been committed.

出现写入倾斜当每笔单独的交易遵守所需的不变量时，但它们的组合不满足这些不变量。例如，交易和修改两个账户和的值。开始于并开始于. 账户价值允许为负数，只要两个账户的总和为非负数：。和分别尝试退出和。由于这些交易开始时，总共可用。两个事务都假设它们保留了不变量并且允许提交。提交后，has和hasT1T2A1A2A1100$A2150$A1 + A2 >= 0T1T2200$A1A2A1 + A2 = 250$250$A1-100$A2-50$，这显然违反了保持账户总金额为正的要求[FEKETE04]。

A write skew occurs when each individual transaction respects the required invariants, but their combination does not satisfy these invariants. For example, transactions T1 and T2 modify values of two accounts A1 and A2. A1 starts with 100$ and A2 starts with 150$. The account value is allowed to be negative, as long as the sum of the two accounts is nonnegative: A1 + A2 >= 0. T1 and T2 each attempt to withdraw 200$ from A1 and A2, respectively. Since at the time these transactions start A1 + A2 = 250$, 250$ is available in total. Both transactions assume they’re preserving the invariant and are allowed to commit. After the commit, A1 has -100$ and A2 has -50$, which clearly violates the requirement to keep a sum of the accounts positive [FEKETE04].

隔离级别

Isolation Levels

这最低（换句话说，最弱）隔离级别是未提交读取。在此隔离级别下，事务系统允许一个事务观察其他并发事务未提交的更改。换句话说，脏读是允许的。

The lowest (in other words, weakest) isolation level is read uncommitted. Under this isolation level, the transactional system allows one transaction to observe uncommitted changes of other concurrent transactions. In other words, dirty reads are allowed.

我们可以避免一些异常情况。例如，我们可以确保特定事务执行的任何读取只能读取已经提交的更改。但是，不能保证如果事务在稍后阶段再次尝试读取相同的数据记录，它将看到相同的值。如果两次读取之间存在已提交的修改，则同一事务中的两个查询将产生不同的结果。换句话说，不允许脏读，但允许幻读和不可重复读。这隔离级别称为读已提交。如果我们进一步禁止不可重复读取，我们获得可重复的读隔离级别。

We can avoid some of the anomalies. For example, we can make sure that any read performed by the specific transaction can only read already committed changes. However, it is not guaranteed that if the transaction attempts to read the same data record once again at a later stage, it will see the same value. If there was a committed modification between two reads, two queries in the same transaction would yield different results. In other words, dirty reads are not permitted, but phantom and nonrepeatable reads are. This isolation level is called read committed. If we further disallow nonrepeatable reads, we get a repeatable read isolation level.

最强的隔离级别是可串行化。正如我们在“可串行性”中已经讨论过的，它保证事务结果将以某种顺序出现，就好像事务是串行执行的（即，时间上没有重叠）。禁止并发执行会对数据库性能产生重大负面影响。只要事务的内部不变量保持并且可以并发执行，事务就可以重新排序，但它们的结果必须以某种串行顺序出现。

The strongest isolation level is serializability. As we already discussed in “Serializability”, it guarantees that transaction outcomes will appear in some order as if transactions were executed serially (i.e., without overlapping in time). Disallowing concurrent execution would have a substantial negative impact on the database performance. Transactions can get reordered, as long as their internal invariants hold and can be executed concurrently, but their outcomes have to appear in some serial order.

图 5-5显示了隔离级别及其允许的异常情况。

Figure 5-5 shows isolation levels and the anomalies they allow.

图 5-5。隔离级别和允许的异常

没有依赖性的事务可以按任何顺序执行，因为它们的结果是完全独立的。不像线性化（我们在分布式系统的上下文中讨论；请参阅“线性化” ），可串行化是以任意顺序执行的多个操作的属性。它并不暗示或试图对执行交易强加任何特定的顺序。隔离于ACID 术语意味着可串行化[BAILIS14a]。不幸的是，实现可串行性需要协调。换句话说，并发执行的事务必须协调以保留不变量，并对冲突的执行施加串行顺序[BAILIS14b]。

Transactions that do not have dependencies can be executed in any order since their results are fully independent. Unlike linearizability (which we discuss in the context of distributed systems; see “Linearizability”), serializability is a property of multiple operations executed in arbitrary order. It does not imply or attempt to impose any particular order on executing transactions. Isolation in ACID terms means serializability [BAILIS14a]. Unfortunately, implementing serializability requires coordination. In other words, transactions executing concurrently have to coordinate to preserve invariants and impose a serial order on conflicting executions [BAILIS14b].

一些数据库使用快照隔离。在快照隔离下，事务可以观察在其启动时提交的所有事务所执行的状态更改。每个事务都会获取数据快照并对其执行查询。该快照在事务执行期间不能更改。仅当事务所修改的值在执行时未发生更改时，事务才会提交。否则，它将中止并回滚。

Some databases use snapshot isolation. Under snapshot isolation, a transaction can observe the state changes performed by all transactions that were committed by the time it has started. Each transaction takes a snapshot of data and executes queries against it. This snapshot cannot change during transaction execution. The transaction commits only if the values it has modified did not change while it was executing. Otherwise, it is aborted and rolled back.

如果两个事务尝试修改相同的值，则只允许其中一个事务提交。这防止丢失更新异常。例如，事务和都尝试修改. 他们从快照中读取当前值，该快照包含在启动之前提交的所有事务的更改。无论哪个事务首先尝试提交，都会提交，而另一个事务则必须中止。失败的事务将重试而不是覆盖该值。T1T2VV

If two transactions attempt to modify the same value, only one of them is allowed to commit. This precludes a lost update anomaly. For example, transactions T1 and T2 both attempt to modify V. They read the current value of V from the snapshot that contains changes from all transactions that were committed before they started. Whichever transaction attempts to commit first, will commit, and the other one will have to abort. The failed transactions will retry instead of overwriting the value.

写入倾斜异常在快照隔离下是可能的，因为如果两个事务从本地状态读取、修改独立记录并保留本地不变量，则它们都被允许提交[FEKETE04]。我们在“使用 Percolator 进行分布式事务”中的分布式事务上下文中更详细地讨论了快照隔离。

A write skew anomaly is possible under snapshot isolation, since if two transactions read from local state, modify independent records, and preserve local invariants, they both are allowed to commit [FEKETE04]. We discuss snapshot isolation in more detail in the context of distributed transactions in “Distributed Transactions with Percolator”.

乐观并发控制

Optimistic Concurrency Control

乐观并发控制假设事务冲突很少发生，我们可以验证事务以防止与并发执行的事务发生读/写冲突，并在提交结果之前确保可串行性，而不是使用锁和阻止事务执行。一般来说，交易执行分为三个阶段[WEIKUM01]：

Optimistic concurrency control assumes that transaction conflicts occur rarely and, instead of using locks and blocking transaction execution, we can validate transactions to prevent read/write conflicts with concurrently executing transactions and ensure serializability before committing their results. Generally, transaction execution is split into three phases [WEIKUM01]:

读取阶段

Read phase

这事务在其自己的私有上下文中执行其步骤，而不使任何更改对其他事务可见。在此步骤之后，所有事务依赖性（读集）以及事务产生的副作用（写集）都已知。

The transaction executes its steps in its own private context, without making any of the changes visible to other transactions. After this step, all transaction dependencies (read set) are known, as well as the side effects the transaction produces (write set).

验证阶段

Validation phase

读检查并发事务的写入集，以确定其操作之间是否存在可能违反可串行性的冲突。如果事务正在读取的某些数据现在已过时，或者它将覆盖在其读取阶段提交的事务写入的某些值，则其私有上下文将被清除并重新启动读取阶段。换句话说，验证阶段确定提交事务是否保留 ACID 属性。

Read and write sets of concurrent transactions are checked for the presence of possible conflicts between their operations that might violate serializability. If some of the data the transaction was reading is now out-of-date, or it would overwrite some of the values written by transactions that committed during its read phase, its private context is cleared and the read phase is restarted. In other words, the validation phase determines whether or not committing the transaction preserves ACID properties.

写入阶段

Write phase

如果验证阶段尚未确定任何冲突，事务可以将其写入集从私有上下文提交到数据库状态。

If the validation phase hasn’t determined any conflicts, the transaction can commit its write set from the private context to the database state.

验证可以通过检查与已提交的事务（向后导向）或当前处于验证阶段的事务（向前导向）的冲突来完成。不同事务的验证和写入阶段应该以原子方式完成。当其他事务正在验证时，不允许提交任何事务。由于验证和写入阶段通常比读取阶段短，因此这是一个可以接受的折衷方案。

Validation can be done by checking for conflicts with the transactions that have already been committed (backward-oriented), or with the transactions that are currently in the validation phase (forward-oriented). Validation and write phases of different transactions should be done atomically. No transaction is allowed to commit while some other transaction is being validated. Since validation and write phases are generally shorter than the read phase, this is an acceptable compromise.

向后导向的并发控制确保对于任何一对事务和，以下属性成立：T1T2

Backward-oriented concurrency control ensures that for any pair of transactions T1 and T2, the following properties hold:

• T1在读取阶段开始之前提交，因此允许提交。T2T2

• T1 was committed before the read phase of T2 began, so T2 is allowed to commit.

• T1在写入阶段之前提交，并且写入集与读取集不相交。换句话说，没有写任何应该看到的值。T2T1T2T1T2

• T1 was committed before the T2 write phase, and the write set of T1 doesn’t intersect with the T2 read set. In other words, T1 hasn’t written any values T2 should have seen.

• 的读取阶段已在 的读取阶段之前完成，并且 的写入集与 的读取或写入集不相交。换句话说，事务是对独立的数据记录集进行操作的，因此都允许提交。T1T2T2T1

• The read phase of T1 has completed before the read phase of T2, and the write set of T2 doesn’t intersect with the read or write sets of T1. In other words, transactions have operated on independent sets of data records, so both are allowed to commit.

如果验证通常成功并且不必重试事务，则此方法非常有效，因为重试会对性能产生显着的负面影响。当然乐观并发还是有一个临界区，事务一次只能进入一个。允许某些操作非独占所有权的另一种方法是使用读写锁（以允许读者共享访问）和可升级锁（以允许在需要时将共享锁转换为独占锁）。

This approach is efficient if validation usually succeeds and transactions don’t have to be retried, since retries have a significant negative impact on performance. Of course, optimistic concurrency still has a critical section, which transactions can enter one at a time. Another approach that allows nonexclusive ownership for some operations is to use readers-writer locks (to allow shared access for readers) and upgradeable locks (to allow conversion of shared locks to exclusive when needed).

多版本并发控制

Multiversion Concurrency Control

多版本并发控制是通过允许多个记录版本并使用单调递增的事务 ID 或时间戳来实现数据库管理系统中事务一致性的一种方法。这允许读取和写入在存储级别上以最小的协调进行，因为读取可以继续访问旧值，直到提交新值。

Multiversion concurrency control is a way to achieve transactional consistency in database management systems by allowing multiple record versions and using monotonically incremented transaction IDs or timestamps. This allows reads and writes to proceed with a minimal coordination on the storage level, since reads can continue accessing older values until the new ones are committed.

MVCC区分已提交和未提交版本，分别对应已提交和未提交事务的值版本。该值的最后提交版本被假定为current。一般来说，在这种情况下，事务管理器的目标是一次最多拥有一个未提交的值。

MVCC distinguishes between committed and uncommitted versions, which correspond to value versions of committed and uncommitted transactions. The last committed version of the value is assumed to be current. Generally, the goal of the transaction manager in this case is to have at most one uncommitted value at a time.

根据数据库系统实现的隔离级别，读操作可能被允许也可能不允许访问未提交的值[WEIKUM01]。多版本并发可以使用锁定、调度和冲突解决技术（例如两阶段锁定）或时间戳排序来实现。MVCC 实现快照隔离的主要用例之一[HELLERSTEIN07]。

Depending on the isolation level implemented by the database system, read operations may or may not be allowed to access uncommitted values [WEIKUM01]. Multiversion concurrency can be implemented using locking, scheduling, and conflict resolution techniques (such as two-phase locking), or timestamp ordering. One of the major use cases for MVCC for implementing snapshot isolation [HELLERSTEIN07].

悲观并发控制

Pessimistic Concurrency Control

悲观并发控制计划比乐观计划更为保守。这些方案在运行时确定事务冲突并阻止或中止其执行。

Pessimistic concurrency control schemes are more conservative than optimistic ones. These schemes determine transaction conflicts while they’re running and block or abort their execution.

一最简单的悲观（无锁）并发控制方案是时间戳排序，其中每个事务都有一个时间戳。是否允许执行事务操作取决于是否已经提交了时间戳较早的事务。为了实现这一点，事务管理器必须维护max_read_timestamp每个max_write_timestamp值，描述并发事务执行的读取和写入操作。

One of the simplest pessimistic (lock-free) concurrency control schemes is timestamp ordering, where each transaction has a timestamp. Whether or not transaction operations are allowed to be executed is determined by whether or not any transaction with an earlier timestamp has already been committed. To implement that, the transaction manager has to maintain max_read_timestamp and max_write_timestamp per value, describing read and write operations executed by concurrent transactions.

尝试读取时间戳低于 的值的读取max_write_timestamp操作会导致它们所属的事务中止，因为已经存在更新的值，并且允许此操作将违反事务顺序。

Read operations that attempt to read a value with a timestamp lower than max_write_timestamp cause the transaction they belong to be aborted, since there’s already a newer value, and allowing this operation would violate the transaction order.

同样，时间戳低于的写入max_read_timestamp操作会与最近的读取发生冲突。但是，允许时间戳低于的写入max_write_timestamp操作，因为我们可以安全地忽略过时的写入值。这猜想通常称为托马斯写规则 [THOMAS79]。一旦执行读或写操作，相应的最大时间戳值就会更新。中止的事务会以新的时间戳重新启动，否则它们肯定会再次中止[RAMAKRISHNAN03]。

Similarly, write operations with a timestamp lower than max_read_timestamp would conflict with a more recent read. However, write operations with a timestamp lower than max_write_timestamp are allowed, since we can safely ignore the outdated written values. This conjecture is commonly called the Thomas Write Rule [THOMAS79]. As soon as read or write operations are performed, the corresponding maximum timestamp values are updated. Aborted transactions restart with a new timestamp, since otherwise they’re guaranteed to be aborted again [RAMAKRISHNAN03].

基于锁的并发控制

Lock-Based Concurrency Control

基于锁的并发控制方案是悲观并发控制的一种形式，它在数据库对象上使用显式锁定，而不是像时间戳排序等协议那样解析调度。使用锁的一些缺点是争用和可扩展性问题[REN16]。

Lock-based concurrency control schemes are a form of pessimistic concurrency control that uses explicit locks on the database objects rather than resolving schedules, like protocols such as timestamp ordering do. Some of the downsides of using locks are contention and scalability issues [REN16].

一最广泛的基于锁的技术是两阶段锁定(2PL)，它将锁管理分为两个阶段：

One of the most widespread lock-based techniques is two-phase locking (2PL), which separates lock management into two phases:

• 这 增长阶段（也称为扩展阶段），在此期间获取事务所需的所有锁，并且不释放任何锁。

• The growing phase (also called the expanding phase), during which all locks required by the transaction are acquired and no locks are released.

• 这 收缩阶段，在此期间释放在增长阶段获取的所有锁。

• The shrinking phase, during which all locks acquired during the growing phase are released.

从这两个定义得出的一条规则是，事务一旦释放了至少一个锁，就无法立即获取任何锁。值得注意的是，2PL 并不排除事务在这些阶段之一期间执行步骤；然而，某些 2PL 变体（例如保守的 2PL）确实施加了这些限制。

A rule that follows from these two definitions is that a transaction cannot acquire any locks as soon as it has released at least one of them. It’s important to note that 2PL does not preclude transactions from executing steps during either one of these phases; however, some 2PL variants (such as conservative 2PL) do impose these limitations.

僵局

Deadlocks

在在锁定协议中，事务尝试获取数据库对象上的锁，如果不能立即授予锁，则事务必须等待锁被释放。当两个事务尝试获取继续执行所需的锁时，可能会出现一种情况，最终等待对方释放它们持有的其他锁。这种情况称为死锁。

In locking protocols, transactions attempt to acquire locks on the database objects and, in case a lock cannot be granted immediately, a transaction has to wait until the lock is released. A situation may occur when two transactions, while attempting to acquire locks they require in order to proceed with execution, end up waiting for each other to release the other locks they hold. This situation is called a deadlock.

图5-6显示了死锁的示例：持有锁并等待锁释放，同时持有锁并等待释放。T1L1L2T2L2L1

Figure 5-6 shows an example of a deadlock: T1 holds lock L1 and waits for lock L2 to be released, while T2 holds lock L2 and waits for L1 to be released.

图 5-6。死锁示例

处理死锁的最简单方法是引入超时并中止长时间运行的事务（假设它们可能处于死锁状态）。另一种策略，保守的2PL，要求事务在执行任何操作之前获取所有锁，如果不能则中止。然而，这些方法极大地限制了系统并发性，并且数据库系统大多使用事务管理器检测或避免（换句话说，防止）死锁。

The simplest way to handle deadlocks is to introduce timeouts and abort long-running transactions under the assumption that they might be in a deadlock. Another strategy, conservative 2PL, requires transactions to acquire all the locks before they can execute any of their operations and abort if they cannot. However, these approaches significantly limit system concurrency, and database systems mostly use a transaction manager to detect or avoid (in other words, prevent) deadlocks.

检测死锁通常使用等待图来完成，该图跟踪正在进行的事务之间的关系并在它们之间建立等待关系。

Detecting deadlocks is generally done using a waits-for graph, which tracks relationships between the in-flight transactions and establishes waits-for relationships between them.

该图中的循环表明存在死锁：事务正在等待，而事务又在等待。死锁检测可以定期（每个时间间隔一次）或连续（每次更新等待图时）进行[WEIKUM01]。其中一项事务（通常是最近尝试获取锁的事务）被中止。T1T2T1

Cycles in this graph indicate the presence of a deadlock: transaction T1 is waiting for T2 which, in turn, waits for T1. Deadlock detection can be done periodically (once per time interval) or continuously (every time the waits-for graph is updated) [WEIKUM01]. One of the transactions (usually, the one that attempted to acquire the lock more recently) is aborted.

为了避免死锁并将锁获取限制在不会导致死锁的情况下，事务管理器可以使用事务时间戳来确定其优先级。较低的时间戳通常意味着较高的优先级，反之亦然。

To avoid deadlocks and restrict lock acquisition to cases that will not result in a deadlock, the transaction manager can use transaction timestamps to determine their priority. A lower timestamp usually implies higher priority and vice versa.

如果事务尝试获取当前由 持有的锁，并且具有更高的优先级（它在 之前开始），我们可以使用以下限制之一来避免死锁[RAMAKRISHNAN03]：T1T2T1T2

If transaction T1 attempts to acquire a lock currently held by T2, and T1 has higher priority (it started before T2), we can use one of the following restrictions to avoid deadlocks [RAMAKRISHNAN03]:

等死

Wait-die

T1被允许阻塞并等待锁。否则，T ₁被中止并重新启动。换句话说，只有具有更高时间戳的事务才能阻止事务。

T1 is allowed to block and wait for the lock. Otherwise, T₁ is aborted and restarted. In other words, a transaction can be blocked only by a transaction with a higher timestamp.

伤口等待

Wound-wait

T2被中止并重新开始（伤口）。否则（如果之前已经开始），是允许的T1 T2T2T1T1等待。换句话说，一个事务只能被时间戳较小的事务阻塞。

T2 is aborted and restarted (T1 wounds T2). Otherwise (if T2 has started before T1), T1 is allowed to wait. In other words, a transaction can be blocked only by a transaction with a lower timestamp.

事务处理需要调度程序来处理死锁。同时，锁存器（参见“锁存器”）依赖于程序员来确保死锁不会发生，而不依赖于死锁避免机制。

Transaction processing requires a scheduler to handle deadlocks. At the same time, latches (see “Latches”) rely on the programmer to ensure that deadlocks cannot happen and do not rely on deadlock avoidance mechanisms.

读写锁

Readers-writer lock

这最简单的闩锁实现将向请求线程授予独占读/写访问权限。然而，大多数时候，我们不需要将所有进程相互隔离。例如，读取可以并发访问页面而不会造成任何麻烦，因此我们只需要确保多个并发写入者不重叠，并且读取器与写入者不重叠。为了实现这种粒度级别，我们可以使用读写锁或 RW 锁。

The simplest latch implementation would grant exclusive read/write access to the requesting thread. However, most of the time, we do not need to isolate all the processes from each other. For example, reads can access pages concurrently without causing any trouble, so we only need to make sure that multiple concurrent writers do not overlap, and readers do not overlap with writers. To achieve this level of granularity, we can use a readers-writer lock or RW lock.

RW 锁允许多个读取者同时访问该对象，并且只有写入者（通常数量较少）必须获得对该对象的独占访问权。图 5-7显示了读写锁的兼容性表：只有读取者可以共享锁所有权，而所有其他读取者和写入者组合都应获得独占所有权。

An RW lock allows multiple readers to access the object concurrently, and only writers (which we usually have fewer of) have to obtain exclusive access to the object. Figure 5-7 shows the compatibility table for readers-writer locks: only readers can share lock ownership, while all other combinations of readers and writers should obtain exclusive ownership.

图 5-7。读写锁兼容性表

在图 5-8 (a) 中，我们有多个读取器访问该对象，而写入器正在等待轮到它，因为当读取器访问页面时它无法修改页面。在图5-8 (b)中，writer 1持有对象的独占锁，而另一个写入者和三个读取者必须等待。

In Figure 5-8 (a), we have multiple readers accessing the object, while the writer is waiting for its turn, since it can’t modify the page while readers access it. In Figure 5-8 (b), writer 1 holds an exclusive lock on the object, while another writer and three readers have to wait.

图 5-8。读写锁

由于尝试访问同一页面的两个重叠读取除了防止页面缓存两次从磁盘获取页面之外不需要同步，因此可以在共享模式下安全地并发执行读取。一旦写入开始发挥作用，我们就需要将它们与并发读取和其他写入隔离。

Since two overlapping reads attempting to access the same page do not require synchronization other than preventing the page from being fetched from disk by the page cache twice, reads can be safely executed concurrently in shared mode. As soon as writes come into play, we need to isolate them from both concurrent reads and other writes.

闩锁捕蟹

Latch crabbing

这获取锁存器的最直接方法是获取从根到目标叶的途中的所有锁存器。这会产生并发瓶颈，在大多数情况下是可以避免的。应尽量减少保持锁存器的时间。可用于实现这一目标的优化之一称为闩锁蟹控（或闩锁耦合）[RAMAKRISHNAN03]。

The most straightforward approach for latch acquisition is to grab all the latches on the way from the root to the target leaf. This creates a concurrency bottleneck and can be avoided in most cases. The time during which a latch is held should be minimized. One of the optimizations that can be used to achieve that is called latch crabbing (or latch coupling) [RAMAKRISHNAN03].

闩锁蟹蟹是一种相当简单的方法，它允许保持闩锁的时间较短，并在明确执行操作不再需要它们时立即释放它们。在读路径上，一旦找到子节点并获取其锁存器，就可以释放父节点的锁存器。

Latch crabbing is a rather simple method that allows holding latches for less time and releasing them as soon as it’s clear that the executing operation does not require them anymore. On the read path, as soon as the child node is located and its latch is acquired, the parent node’s latch can be released.

在插入期间，如果保证操作不会导致可以传播到它的结构更改，则可以释放父锁存器。换句话说，如果子节点未满，则可以释放父锁存器。

During insert, the parent latch can be released if the operation is guaranteed not to result in structural changes that can propagate to it. In other words, the parent latch can be released if the child node is not full.

类似地，在删除过程中，如果子节点持有足够的元素并且操作不会导致兄弟节点合并，则释放父节点上的闩锁。

Similarly, during deletes, if the child node holds enough elements and the operation will not cause sibling nodes to merge, the latch on the parent node is released.

图 5-9显示了插入期间从根到叶的传递：

Figure 5-9 shows a root-to-leaf pass during insert:

• a) 在根级别获取写锁存器。

• a) The write latch is acquired on the root level.

• b) 定位下一级节点，并获取其写锁存器。检查节点是否存在潜在的结构变化。由于节点未满，因此可以释放父锁存器。

• b) The next-level node is located, and its write latch is acquired. The node is checked for potential structural changes. Since the node is not full, the parent latch can be released.

• c) 操作下降到下一个级别。获取写锁存器，检查目标叶节点是否有潜在的结构变化，并释放父锁存器。

• c) The operation descends to the next level. The write latch is acquired, the target leaf node is checked for potential structural changes, and the parent latch is released.

这种方法是乐观的：大多数插入和删除操作不会导致向上传播多个级别的结构变化。事实上，结构变化的可能性在较高水平上会降低。大多数操作只需要目标节点上的latch，并且需要保留父latch的情况相对较少。

This approach is optimistic: most insert and delete operations do not cause structural changes that propagate multiple levels up. In fact, the probability of structural changes decreases at higher levels. Most of the operations only require the latch on the target node, and the number of cases when the parent latch has to be retained is relatively small.

如果子页面仍未加载到页面缓存中，我们可以锁存将来加载的页面，或者释放父锁存器并在页面加载后重新启动根到叶传递以减少争用。重新启动根到叶的遍历听起来相当昂贵，但实际上，我们必须很少执行它，并且可以采用机制来检测自遍历以来更高级别是否存在任何结构变化[GRAEFE10 ]。

If the child page is still not loaded in the page cache, we can either latch a future loading page, or release a parent latch and restart the root-to-leaf pass after the page is loaded to reduce contention. Restarting root-to-leaf traversal sounds rather expensive, but in reality, we have to perform it rather infrequently, and can employ mechanisms to detect whether or not there were any structural changes at higher levels since the time of traversal [GRAEFE10].

图 5-9。插入期间闩锁偏斜

连线虎

WiredTiger

让我们看看我们如何使用缓冲来实现惰性 B 树。为此，我们可以在 B 树节点被分页后立即在内存中具体化它们，并使用此结构来存储更新，直到我们准备好刷新它们为止。

Let’s take a look at how we can use buffering to implement a lazy B-Tree. For that, we can materialize B-Tree nodes in memory as soon as they are paged in and use this structure to store updates until we’re ready to flush them.

WiredTiger使用了类似的方法，它是现在默认的 MongoDB 存储引擎。它的行存储 B-Tree 实现对内存中和磁盘上的页面使用不同的格式。在内存中的页面被持久化之前，它们必须经历协调过程。

A similar approach is used by WiredTiger, a now-default MongoDB storage engine. Its row store B-Tree implementation uses different formats for in-memory and on-disk pages. Before in-memory pages are persisted, they have to go through the reconciliation process.

在图 6-2中，您可以看到 WiredTiger 页面及其在 B 树中的组成的示意图。A 干净页仅包含一个索引，该索引最初是根据磁盘上的页映像构建的。更新首先保存到更新缓冲区中。

In Figure 6-2, you can see a schematic representation of WiredTiger pages and their composition in a B-Tree. A clean page consists of just an index, initially constructed from the on-disk page image. Updates are first saved into the update buffer.

图 6-2。WiredTiger：高级概述

更新缓冲区在读取期间被访问：它们的内容与原始磁盘页面内容合并以返回最新数据。刷新页面时，更新缓冲区内容与页面内容一致并保留在磁盘上，覆盖原始页面。如果协调页面的大小大于最大值，则会将其拆分为多个页面。更新缓冲区是使用实现的跳跃列表，其复杂性类似于搜索树[PAPADAKIS93]，但具有更好的并发配置文件[PUGH90a]。

Update buffers are accessed during reads: their contents are merged with the original on-disk page contents to return the most recent data. When the page is flushed, update buffer contents are reconciled with page contents and persisted on disk, overwriting the original page. If the size of the reconciled page is greater than the maximum, it is split into multiple pages. Update buffers are implemented using skiplists, which have a complexity similar to search trees [PAPADAKIS93] but have a better concurrency profile [PUGH90a].

图 6-3显示 WiredTiger 中的干净页和脏页都有内存版本，并引用磁盘上的基础映像。除此之外，脏页还有一个更新缓冲区。

Figure 6-3 shows that both clean and dirty pages in WiredTiger have in-memory versions, and reference a base image on disk. Dirty pages have an update buffer in addition to that.

这里的主要优点是页面更新和结构修改（拆分和合并）由后台线程执行，读/写过程不必等待它们完成。

The main advantage here is that the page updates and structural modifications (splits and merges) are performed by the background thread, and read/write processes do not have to wait for them to complete.

图 6-3。WiredTiger 页面

惰性自适应树

Lazy-Adaptive Tree

相当与缓冲对单个节点的更新相比，我们可以将节点分组为子树，并将用于批处理操作的更新缓冲区附加到每个子树。在这种情况下，更新缓冲区将跟踪针对子树顶部节点及其后代执行的所有操作。该算法称为惰性自适应树（LA-Tree）[AGRAWAL09]。

Rather than buffering updates to individual nodes, we can group nodes into subtrees, and attach an update buffer for batching operations to each subtree. Update buffers in this case will track all operations performed against the subtree top node and its descendants. This algorithm is called Lazy-Adaptive Tree (LA-Tree) [AGRAWAL09].

当插入数据记录时，首先将新条目添加到根节点更新缓冲区中。当该缓冲区变满时，通过将更改复制并传播到较低树级别中的缓冲区来清空该缓冲区。如果较低层也填满，则该操作可以递归地继续，直到最终到达叶节点。

When inserting a data record, a new entry is first added to the root node update buffer. When this buffer becomes full, it is emptied by copying and propagating the changes to the buffers in the lower tree levels. This operation can continue recursively if the lower levels fill up as well, until it finally reaches the leaf nodes.

在图 6-4中，您可以看到 LA 树，其节点具有级联缓冲区，这些节点分组在相应的子树中。灰色框表示从根缓冲区传播的更改。

In Figure 6-4, you see an LA-Tree with cascaded buffers for nodes grouped in corresponding subtrees. Gray boxes represent changes that propagated from the root buffer.

图 6-4。洛杉矶树

缓冲区具有层次依赖性并且是级联的：所有更新都从较高级别的缓冲区传播到较低级别的缓冲区。当更新到达叶级别时，将在那里执行批量插入、更新和删除操作，立即将所有更改应用于树内容及其结构。页面可以在单次运行中更新，而不是单独对页面执行后续更新，从而需要更少的磁盘访问和结构更改，因为拆分和合并也会批量传播到更高级别。

Buffers have hierarchical dependencies and are cascaded: all the updates propagate from higher-level buffers to the lower-level ones. When the updates reach the leaf level, batched insert, update, and delete operations are performed there, applying all changes to the tree contents and its structure at once. Instead of performing subsequent updates on pages separately, pages can be updated in a single run, requiring fewer disk accesses and structural changes, since splits and merges propagate to the higher levels in batches as well.

这里描述的缓冲方法通过批处理写入操作来优化树更新时间，但方式略有不同。这两种算法都需要在内存缓冲结构中进行额外的查找，并与陈旧的磁盘数据进行合并/协调。

The buffering approaches described here optimize tree update time by batching write operations, but in slightly different ways. Both algorithms require additional lookups in in-memory buffering structures and merge/reconciliation with stale disk data.

分数级联

Fractional Cascading

到为了维护级别之间的指针，FD-Tree 使用一种称为分数级联的技术 [CHAZELLE86]。这种方法有助于降低在级联排序数组中定位项目的成本：您执行log n步骤在第一个数组中查找搜索项目，但后续搜索的成本要低得多，因为它们从前一个数组中最接近的匹配开始搜索等级。

To maintain pointers between the levels, FD-Trees use a technique called fractional cascading [CHAZELLE86]. This approach helps to reduce the cost of locating an item in the cascade of sorted arrays: you perform log n steps to find the searched item in the first array, but subsequent searches are significantly cheaper, since they start the search from the closest match from the previous level.

级别之间的快捷方式由在相邻级数组之间建立桥梁以最小化间隙：没有来自更高级别的指针的元素组。桥是通过将元素从较低级别拉到较高级别（如果这些元素尚不存在）并指向较低级别数组中所拉元素的位置来构建的。

Shortcuts between the levels are made by building bridges between the neighbor-level arrays to minimize the gaps: element groups without pointers from higher levels. Bridges are built by pulling elements from lower levels to the higher ones, if they don’t already exist there, and pointing to the location of the pulled element in the lower-level array.

由于[CHAZELLE86]解决了计算几何中的搜索问题，因此它描述了双向桥，以及用于恢复间隙大小不变量的算法，我们不会在这里介绍。我们仅描述适用于数据库存储的部分，特别是 FD-Tree。

Since [CHAZELLE86] solves a search problem in computational geometry, it describes bidirectional bridges, and an algorithm for restoring the gap size invariant that we won’t be covering here. We describe only the parts that are applicable to database storage and FD-Trees in particular.

我们可以创建从较高级别数组的每个元素到下一级最接近元素的映射，但这会导致指针及其维护产生过多的开销。如果我们只映射更高级别上已经存在的项目，我们最终可能会遇到元素之间的间隙过大的情况。为了解决这个问题，我们将N低层数组中的每一项都拉到高层数组中。

We could create a mapping from every element of the higher-level array to the closest element on the next level, but that would cause too much overhead for pointers and their maintenance. If we were to map only the items that already exist on a higher level, we could end up in a situation where the gaps between the elements are too large. To solve this problem, we pull every Nth item from the lower-level array to the higher one.

例如，如果我们有多个排序数组：

For example, if we have multiple sorted arrays:

A1 = [12, 24, 32, 34, 39]
A2 = [22, 25, 28, 30, 35]
A3 = [11, 16, 24, 26, 30]

A1 = [12, 24, 32, 34, 39]
A2 = [22, 25, 28, 30, 35]
A3 = [11, 16, 24, 26, 30]

我们可以通过将索引较高的数组中的所有其他元素拉到索引较低的数组中来弥合元素之间的差距，以简化搜索：

We can bridge the gaps between elements by pulling every other element from the array with a higher index to the one with a lower index in order to simplify searches:

A1 = [12, 24, 25, 30, 32, 34, 39]
A2 = [16, 22, 25, 26, 28, 30, 35]
A3 = [11, 16, 24, 26, 30]

A1 = [12, 24, 25, 30, 32, 34, 39]
A2 = [16, 22, 25, 26, 28, 30, 35]
A3 = [11, 16, 24, 26, 30]

现在，我们可以使用这些拉出的元素创建桥梁（或FD-Tree 论文中所说的栅栏）：从较高级别的元素到较低级别的对应元素的指针，如图6-5所示。

Now, we can use these pulled elements to create bridges (or fences as the FD-Tree paper calls them): pointers from higher-level elements to their counterparts on the lower levels, as Figure 6-5 shows.

图 6-5。分数级联

为了搜索所有这些数组中的元素，我们在最高级别执行二分搜索，并且下一级的搜索空间显着减少，因为现在我们通过一座桥转发到搜索项的大致位置。这使我们能够连接多个排序运行并降低在其中搜索的成本。

To search for elements in all these arrays, we perform a binary search on the highest level, and the search space on the next level is reduced significantly, since now we are forwarded to the approximate location of the searched item by following a bridge. This allows us to connect multiple sorted runs and reduce the costs of searching in them.

对数游程

Logarithmic Runs

一个FD-Tree 将分数级联与创建对数大小的排序游程相结合：大小按 因子增加的不可变排序数组k，通过将前一级别与当前级别合并而创建。

An FD-Tree combines fractional cascading with creating logarithmically sized sorted runs: immutable sorted arrays with sizes increasing by a factor of k, created by merging the previous level with the current one.

当头树变满时，将创建最高级别的运行：其叶内容被写入第一级别。一旦头树再次填满，其内容就会与第一级项目合并。合并结果替换第一次运行的旧版本。当较高级别运行的大小达到阈值时，将创建较低级别的运行。如果较低级别的运行已存在，则将其内容替换为将其内容与较高级别的内容合并的结果。这个过程与 LSM 树中的压缩非常相似，其中不可变的表内容被合并以创建更大的表。

The highest-level run is created when the head tree becomes full: its leaf contents are written to the first level. As soon as the head tree fills up again, its contents are merged with the first-level items. The merged result replaces the old version of the first run. The lower-level runs are created when the sizes of the higher-level ones reach a threshold. If a lower-level run already exists, it is replaced by the result of merging its contents with the contents of a higher level. This process is quite similar to compaction in LSM Trees, where immutable table contents are merged to create larger tables.

图 6-6显示了 FD 树的示意图，顶部有一个头 B 树，两个对数游程L1和L2，以及它们之间的桥。

Figure 6-6 shows a schematic representation of an FD-Tree, with a head B-Tree on the top, two logarithmic runs L1 and L2, and bridges between them.

图 6-6。FD 树概述示意图

为了保持所有排序运行中的项目可寻址，FD-Trees 使用部分级联的改编版本，其中 较低级别页面的头元素作为指向较高级别的指针进行传播。使用这些指针，可以降低在较低级别树中搜索的成本，因为搜索已经在较高级别上部分完成，并且可以从最接近的匹配继续。

To keep items in all sorted runs addressable, FD-Trees use an adapted version of fractional cascading, where head elements from lower-level pages are propagated as pointers to the higher levels. Using these pointers, the cost of searching in lower-level trees is reduced, since the search was already partially done on a higher level and can continue from the closest match.

由于 FD-Tree 不会就地更新页面，并且可能会发生同一键的数据记录存在于多个级别上的情况，因此 FD-Tree 通过插入墓碑来删除工作（FD-Tree 论文称其为 过滤条目），指示与相应键关联的数据记录被标记为删除，并且必须丢弃该键在较低级别中的所有数据记录。当墓碑一直传播到最低层时，它们可以被丢弃，因为可以保证不再有它们可以遮蔽的物品。

Since FD-Trees do not update pages in place, and it may happen that data records for the same key are present on several levels, the FD-Trees delete work by inserting tombstones (the FD-Tree paper calls them filter entries) that indicate that the data record associated with a corresponding key is marked for deletion, and all data records for that key in the lower levels have to be discarded. When tombstones propagate all the way to the lowest level, they can be discarded, since it is guaranteed that there are no items they can shadow anymore.

更新链

Update Chains

ABw-Tree 将基本节点与其修改分开写入。修改（增量节点）形成一条链：从最新修改到较旧修改的链表，最后是基节点。每个更新都可以单独存储，无需重写磁盘上的现有节点。增量节点可以表示插入、更新（与插入没有区别）或删除。

A Bw-Tree writes a base node separately from its modifications. Modifications (delta nodes) form a chain: a linked list from the newest modification, through older ones, with the base node in the end. Each update can be stored separately, without needing to rewrite the existing node on disk. Delta nodes can represent inserts, updates (which are indistinguishable from inserts), or deletes.

由于基本节点和增量节点的大小不太可能页面对齐，因此连续存储它们是有意义的，并且因为更新期间基本节点和增量节点都不会被修改（所有修改只是在现有链表前面添加一个节点），所以我们这样做无需预留任何额外空间。

Since the sizes of base and delta nodes are unlikely to be page aligned, it makes sense to store them contiguously, and because neither base nor delta nodes are modified during update (all modifications just prepend a node to the existing linked list), we do not need to reserve any extra space.

将节点作为逻辑实体而不是物理实体是一个有趣的范式变化：我们不需要预先分配空间，不需要节点具有固定大小，甚至不需要将它们保留在连续的内存段中。这当然有一个缺点：在读取期间，必须遍历所有增量并将其应用于基节点以重建实际的节点状态。这有点类似于 LA-Tree 的做法（请参阅“惰性自适应树”）：将更新与主结构分开并在读取时重放它们。

Having a node as a logical, rather than physical, entity is an interesting paradigm change: we do not need to pre-allocate space, require nodes to have a fixed size, or even keep them in contiguous memory segments. This certainly has a downside: during a read, all deltas have to be traversed and applied to the base node to reconstruct the actual node state. This is somewhat similar to what LA-Trees do (see “Lazy-Adaptive Tree”): keeping updates separate from the main structure and replaying them on read.

通过比较和交换控制并发

Taming Concurrency with Compare-and-Swap

它维护一个允许将项目添加到子节点的磁盘上树结构将是相当昂贵的：它需要我们不断地用指向最新增量的指针更新父节点。这就是为什么 Bw-Tree 节点（由增量链和基节点组成）具有逻辑标识符并使​​用从标识符到它们在磁盘上的位置的内存映射表。使用此映射还可以帮助我们摆脱锁存器：Bw-Tree 在映射表中的物理偏移量上使用比较和交换操作，而不是在写入期间拥有独占所有权。

It would be quite costly to maintain an on-disk tree structure that allows prepending items to child nodes: it would require us to constantly update parent nodes with pointers to the freshest delta. This is why Bw-Tree nodes, consisting of a chain of deltas and the base node, have logical identifiers and use an in-memory mapping table from the identifiers to their locations on disk. Using this mapping also helps us to get rid of latches: instead of having exclusive ownership during write time, the Bw-Tree uses compare-and-swap operations on physical offsets in the mapping table.

图 6-7显示了一个简单的 Bw 树。每个逻辑节点由单个基本节点和多个链接的增量节点组成。

Figure 6-7 shows a simple Bw-Tree. Each logical node consists of a single base node and multiple linked delta nodes.

图 6-7。Bw-树。虚线表示节点之间的虚拟链接，使用映射表解析。实线表示节点之间的实际数据指针。

为了更新 Bw-Tree 节点，算法执行以下步骤：

To update a Bw-Tree node, the algorithm executes the following steps:

1. 通过从根到叶遍历树来定位目标逻辑叶节点。映射表包含到更新链中的目标基本节点或最新增量节点的虚拟链接。

2. The target logical leaf node is located by traversing the tree from root to leaf. The mapping table contains virtual links to target base nodes or the latest delta nodes in the update chain.

3. 创建一个新的增量节点，其中包含指向步骤 1 中找到的基节点（或最新增量节点）的指针。

4. A new delta node is created with a pointer to the base node (or to the latest delta node) located during step 1.

5. 映射表使用指向步骤 2 中创建的新增量节点的指针进行更新。

6. The mapping table is updated with a pointer to the new delta node created during step 2.

步骤 3 期间的更新操作可以使用比较和交换来完成，这是一个原子操作，因此与指针更新并发的所有读取都在写入之前或之后排序，而不会阻塞读取器或写入器。之前订购的读取遵循旧指针，看不到新的增量节点，因为它尚未安装。跟随新指针有序读取，并观察更新情况。如果两个线程尝试将新的增量节点安装到同一逻辑节点，则只有其中一个可以成功，另一个线程必须重试该操作。

An update operation during step 3 can be done using compare-and-swap, which is an atomic operation, so all reads, concurrent to the pointer update, are ordered either before or after the write, without blocking either the readers or the writer. Reads ordered before follow the old pointer and do not see the new delta node, since it was not yet installed. Reads ordered after follow the new pointer, and observe the update. If two threads attempt to install a new delta node to the same logical node, only one of them can succeed, and the other one has to retry the operation.

结构改造操作

Structural Modification Operations

ABw-Tree 的逻辑结构类似于 B-Tree，这意味着节点仍然可能变得太大（溢出）或缩小到几乎为空（下溢），并且需要结构修改操作 (SMO)，例如拆分和合并。这里的拆分和合并的语义与 B-Tree 类似（参见“B-Tree 节点拆分”和“B-Tree 节点合并”），但它们的实现不同。

A Bw-Tree is logically structured like a B-Tree, which means that nodes still might grow to be too large (overflow) or shrink to be almost empty (underflow) and require structure modification operations (SMOs), such as splits and merges. The semantics of splits and merges here are similar to those of B-Trees (see “B-Tree Node Splits” and “B-Tree Node Merges”), but their implementation is different.

拆分 SMO首先合并分裂节点的逻辑内容，将增量应用到其基本节点，并创建一个包含分裂点右侧元素的新页面。此后，该过程分两步进行[WANG18]：

Split SMOs start by consolidating the logical contents of the splitting node, applying deltas to its base node, and creating a new page containing elements to the right of the split point. After this, the process proceeds in two steps [WANG18]:

1. 分裂—A特殊的分裂增量节点被附加到分裂节点，以通知读者正在进行的分裂。分裂增量节点持有一个中点分隔符键以使分裂节点中的记录无效，以及到新逻辑兄弟节点的链接。

2. Split—A special split delta node is appended to the splitting node to notify the readers about the ongoing split. The split delta node holds a midpoint separator key to invalidate records in the splitting node, and a link to the new logical sibling node.

3. 家长更新— 于此时，情况与B^链接-Tree类似 half-split（参见“Blink-Trees”），因为该节点可以通过分裂增量节点指针获得，但还没有被父节点引用，读者必须先遍历旧节点，然后遍历兄弟指针才能到达新创建的兄弟节点。新节点作为子节点添加到父节点中，这样读者就可以直接到达它，而不是通过分裂节点重定向，分裂完成。

4. Parent update—At this point, the situation is similar to that of the B^link-Tree half-split (see “Blink-Trees”), since the node is available through the split delta node pointer, but is not yet referenced by the parent, and readers have to go through the old node and then traverse the sibling pointer to reach the newly created sibling node. A new node is added as a child to the parent node, so that readers can directly reach it instead of being redirected through the splitting node, and the split completes.

更新父指针是一种性能优化：即使父指针从未更新，所有节点及其元素仍然可访问。Bw-Tree 是无闩锁的，因此任何线程都可能遇到不完整的 SMO。在继续之前，线程需要通过拾取并完成多步骤 SMO 来进行合作。下一个线程将遵循已安装的父指针，而不必通过同级指针。

Updating the parent pointer is a performance optimization: all nodes and their elements remain accessible even if the parent pointer is never updated. Bw-Trees are latch-free, so any thread can encounter an incomplete SMO. The thread is required to cooperate by picking up and finishing a multistep SMO before proceeding. The next thread will follow the installed parent pointer and won’t have to go through the sibling pointer.

合并 SMO以类似的方式工作：

Merge SMOs work in a similar way:

1. 删除同级-A创建特殊的删除增量节点并将其附加到右同级，指示合并 SMO 的开始并将右同级标记为删除。

2. Remove sibling—A special remove delta node is created and appended to the right sibling, indicating the start of the merge SMO and marking the right sibling for deletion.

3. 合并—A 在左同级上创建合并增量节点，以指向右同级的内容，并使其成为左同级的逻辑部分。

4. Merge—A merge delta node is created on the left sibling to point to the contents of the right sibling and making it a logical part of the left sibling.

5. 父更新——此时，可以从左侧访问右侧同级节点的内容。要完成合并过程，必须从父级中删除到右同级的链接。

6. Parent update—At that point, the right sibling node contents are accessible from the left one. To finish the merge process, the link to the right sibling has to be removed from the parent.

并发 SMO 需要在父节点上安装额外的中止增量节点，以防止并发拆分和合并[WANG18]。中止增量的工作方式与写锁类似：一次只有一个线程可以具有写访问权限，并且任何尝试向此增量节点追加新记录的线程都将中止。SMO 完成后，可以从父级中删除中止增量。

Concurrent SMOs require an additional abort delta node to be installed on the parent to prevent concurrent splits and merges [WANG18]. An abort delta works similarly to a write lock: only one thread can have write access at a time, and any thread that attempts to append a new record to this delta node will abort. On SMO completion, the abort delta can be removed from the parent.

Bw-Tree 高度在根节点分裂期间增长。当根节点变得太大时，它会被分成两部分，并创建一个新的根来代替旧的根，并以旧的根和新创建的兄弟作为其子节点。

The Bw-Tree height grows during the root node splits. When the root node gets too big, it is split in two, and a new root is created in place of the old one, with the old root and a newly created sibling as its children.

整合和垃圾收集

Consolidation and Garbage Collection

三角洲链无需任何额外操作即可获得任意长的长度。由于随着 Delta 链变长，读取的成本也越来越高，因此我们需要尝试将 Delta 链长度保持在合理的范围内。当它达到可配置的阈值时，我们通过将基本节点内容与所有增量合并来重建节点，将它们合并到一个新的基本节点。然后，新节点被写入磁盘上的新位置，并且映射表中的节点指针被更新以指向它。我们在“LLAMA 和 Mindful Stacking”中更详细地讨论了这个过程，因为底层日志结构存储负责垃圾收集、节点合并和重新定位。

Delta chains can get arbitrarily long without any additional action. Since reads are getting more expensive as the delta chain gets longer, we need to try to keep the delta chain length within reasonable bounds. When it reaches a configurable threshold, we rebuild the node by merging the base node contents with all of the deltas, consolidating them to one new base node. The new node is then written to the new location on disk and the node pointer in the mapping table is updated to point to it. We discuss this process in more detail in “LLAMA and Mindful Stacking”, as the underlying log-structured storage is responsible for garbage collection, node consolidation, and relocation.

一旦节点被合并，其旧内容（基本节点和所有增量节点）就不再从映射表中寻址。但是，我们无法立即释放它们占用的内存，因为其中一些可能仍在被正在进行的操作使用。由于读取器没有持有锁存器（读取器不必通过或在任何类型的屏障处注册即可访问节点），因此我们需要找到其他方法来跟踪活动页面。

As soon as the node is consolidated, its old contents (the base node and all of the delta nodes) are no longer addressed from the mapping table. However, we cannot free the memory they occupy right away, because some of them might be still used by ongoing operations. Since there are no latches held by readers (readers did not have to pass through or register at any sort of barrier to access the node), we need to find other means to track live pages.

为了将可能遇到特定节点的线程与不可能看到该节点的线程分开，Bw-Trees使用一种称为基于纪元的回收的技术。如果由于在某个时期替换了某些节点和增量而从映射表中删除了某些节点和增量，则原始节点将被保留，直到在同一时期或更早的时期开始的每个读取器完成。之后，它们可以被安全地进行垃圾收集，因为后来的读者保证永远不会看到这些节点，因为在这些读者开始时它们是不可寻址的。

To separate threads that might have encountered a specific node from those that couldn’t have possibly seen it, Bw-Trees use a technique known as epoch-based reclamation. If some nodes and deltas are removed from the mapping table due to consolidations that replaced them during some epoch, original nodes are preserved until every reader that started during the same epoch or the earlier one is finished. After that, they can be safely garbage collected, since later readers are guaranteed to have never seen those nodes, as they were not addressable by the time those readers started.

Bw-Tree 是一个有趣的 B-Tree 变体，在几个重要方面进行了改进：写放大、非阻塞访问和缓存友好性。修改后的版本在Sled中实现，这是一个实验性存储引擎。CMU 数据库组开发了 Bw-Tree 的内存版本，称为OpenBw-Tree，并发布了实用的实施指南[WANG18]。

The Bw-Tree is an interesting B-Tree variant, making improvements on several important aspects: write amplification, nonblocking access, and cache friendliness. A modified version was implemented in Sled, an experimental storage engine. The CMU Database Group has developed an in-memory version of the Bw-Tree called OpenBw-Tree and released a practical implementation guide [WANG18].

我们在本章中只涉及了与 B-Tree 相关的更高级别的 Bw-Tree 概念，我们将在“LLAMA 和 Mindful Stacking”中继续讨论它们，包括对底层日志结构存储的讨论。

We’ve only touched on higher-level Bw-Tree concepts related to B-Trees in this chapter, and we continue the discussion about them in “LLAMA and Mindful Stacking”, including the discussion about the underlying log-structured storage.

范·埃姆德·博阿斯布局

van Emde Boas Layout

A缓存忽略 B 树由静态 B 树和打包数组结构[BENDER05]组成。使用van Emde Boas布局构建静态 B 树。它在边缘的中间层分割树。然后以类似的方式递归地分割每个子树，从而产生sqr(N)大小的子树。这种布局的关键思想是任何递归树都存储在连续的内存块中。

A cache-oblivious B-Tree consists of a static B-Tree and a packed array structure [BENDER05]. A static B-Tree is built using the van Emde Boas layout. It splits the tree at the middle level of the edges. Then each subtree is split recursively in a similar manner, resulting in subtrees of sqr(N) size. The key idea of this layout is that any recursive tree is stored in a contiguous block of memory.

在图 6-8中，您可以看到 van Emde Boas 布局的示例。逻辑上分组在一起的节点紧密地放置在一起。在顶部，您可以看到逻辑布局表示（即节点如何形成树），在底部您可以看到树节点如何在内存和磁盘上布局。

In Figure 6-8, you can see an example of a van Emde Boas layout. Nodes, logically grouped together, are placed closely together. On top, you can see a logical layout representation (i.e., how nodes form a tree), and on the bottom you can see how tree nodes are laid out in memory and on disk.

图 6-8。范·埃姆德·博阿斯布局

为了使数据结构动态化（即允许插入、更新和删除），缓存不经意的树使用打包数组数据结构，该结构使用连续的内存段来存储元素，但包含为将来插入的元素保留的间隙。间隙根据密度阈值进行间隔。图 6-9显示了一个压缩数组结构，其中元素间隔开以形成间隙。

To make the data structure dynamic (i.e., allow inserts, updates, and deletes), cache-oblivious trees use a packed array data structure, which uses contiguous memory segments for storing elements, but contains gaps reserved for future inserted elements. Gaps are spaced based on the density threshold. Figure 6-9 shows a packed array structure, where elements are spaced to create gaps.

图 6-9。压缩数组

这种方法允许以更少的重定位将项目插入到树中。如果间隙尚不存在，则必须重新定位项目才能为新插入的元素创建间隙。当打包数组变得过于密集或稀疏时，必须重建结构以增大或缩小数组。

This approach allows inserting items into the tree with fewer relocations. Items have to be relocated just to create a gap for the newly inserted element, if the gap is not already present. When the packed array becomes too densely or sparsely populated, the structure has to be rebuilt to grow or shrink the array.

静态树用作底层打包数组的索引，并且必须根据重定位的元素进行更新以指向底层的正确元素。

The static tree is used as an index for the bottom-level packed array, and has to be updated in accordance with relocated elements to point to correct elements on the bottom level.

这是一种有趣的方法，其中的想法可用于构建高效的 B 树实现。它允许以与构建主内存结构非常相似的方式构建磁盘结构。然而，截至撰写本文时，我还不知道有任何非学术性的忽略缓存的 B 树实现。

This is an interesting approach, and ideas from it can be used to build efficient B-Tree implementations. It allows constructing on-disk structures in ways that are very similar to how main memory ones are constructed. However, as of the date of writing, I’m not aware of any nonacademic cache-oblivious B-Tree implementations.

一个可能的原因是假设当缓存加载被抽象出来时，当数据以块的形式加载和写回时，分页和逐出仍然会对结果产生负面影响。另一个可能的原因是，就块传输而言，缓存无关的 B 树的复杂性与其缓存感知的对应物相同。当更高效的非易失性字节可寻址存储设备变得更加普遍时，这种情况可能会改变。

A possible reason for that is an assumption that when cache loading is abstracted away, while data is loaded and written back in blocks, paging and eviction still have a negative impact on the result. Another possible reason is that in terms of block transfers, the complexity of cache-oblivious B-Trees is the same as their cache-aware counterpart. This may change when more efficient nonvolatile byte-addressable storage devices become more widespread.

LSM树结构

LSM Tree Structure

我们从有序的 LSM 树[ONEIL96]开始，其中文件保存排序的数据记录。稍后，在“无序LSM存储”中，我们还将讨论允许按插入顺序存储数据记录的结构，这在写入路径上具有一些明显的优势。

We start with ordered LSM Trees [ONEIL96], where files hold sorted data records. Later, in “Unordered LSM Storage”, we’ll also discuss structures that allow storing data records in insertion order, which has some obvious advantages on the write path.

正如我们刚刚讨论的，LSM 树由较小的内存驻留组件和较大的磁盘驻留组件组成。要将不可变的文件内容写到磁盘上，需要首先将它们缓冲在内存中并对其内容进行排序。

As we just discussed, LSM Trees consist of smaller memory-resident and larger disk-resident components. To write out immutable file contents on disk, it is necessary to first buffer them in memory and sort their contents.

A内存驻留组件（通常称为memtable）是可变的：它缓冲数据记录并充当读写操作的目标。当 Memtable 的大小增长到可配置的阈值时，其内容将保留在磁盘上。Memtable 更新不会产生磁盘访问，也没有相关的 I/O 成本。需要一个单独的预写日志文件，类似于我们在“恢复”中讨论的内容，以保证数据记录的持久性。在客户端确认操作之前，数据记录会附加到日志中并提交到内存中。

A memory-resident component (often called a memtable) is mutable: it buffers data records and serves as a target for read and write operations. Memtable contents are persisted on disk when its size grows up to a configurable threshold. Memtable updates incur no disk access and have no associated I/O costs. A separate write-ahead log file, similar to what we discussed in “Recovery”, is required to guarantee durability of data records. Data records are appended to the log and committed in memory before the operation is acknowledged to the client.

缓冲在内存中完成：所有读写操作都应用于内存驻留表，该表维护允许并发访问的排序数据结构，通常是某种形式的内存排序树，或可以提供类似性能特征的任何数据结构。

Buffering is done in memory: all read and write operations are applied to a memory-resident table that maintains a sorted data structure allowing concurrent access, usually some form of an in-memory sorted tree, or any data structure that can give similar performance characteristics.

磁盘驻留组件是由 将内存中缓冲的内容刷新到磁盘。磁盘驻留组件仅用于读取：缓冲的内容被持久化，并且文件永远不会被修改。这使我们能够思考简单的操作：针对内存表进行写入，针对磁盘和基于内存的表进行读取、合并和文件删除。

Disk-resident components are built by flushing contents buffered in memory to disk. Disk-resident components are used only for reads: buffered contents are persisted, and files are never modified. This allows us to think in terms of simple operations: writes against an in-memory table, and reads against disk and memory-based tables, merges, and file removals.

自始至终本章，我们将使用单词table作为磁盘驻留表的快捷方式。由于我们正在讨论存储引擎的语义，因此该术语与更广泛的数据库管理系统上下文中的表概念并无歧义。

Throughout this chapter, we will be using the word table as a shortcut for disk-resident table. Since we’re discussing semantics of a storage engine, this term is not ambiguous with a table concept in the wider context of a database management system.

二元LSM树

Two-component LSM Tree

我们区分双成分和多成分 LSM 树。两部分 LSM 树只有一个磁盘部分，由不可变的段组成。这里的磁盘组件被组织为B-Tree，节点占用率100%，页面只读。

We distinguish between two- and multicomponent LSM Trees. Two-component LSM Trees have only one disk component, comprised of immutable segments. The disk component here is organized as a B-Tree, with 100% node occupancy and read-only pages.

内存驻留树内容部分刷新到磁盘上。在刷新期间，对于每个刷新的内存子树，我们在磁盘上找到对应的子树，并将内存驻留段和磁盘驻留子树的合并内容写入磁盘上的新段。图 7-1显示了合并之前内存中和磁盘驻留的树。

Memory-resident tree contents are flushed on disk in parts. During a flush, for each flushed in-memory subtree, we find a corresponding subtree on disk and write out the merged contents of a memory-resident segment and disk-resident subtree into the new segment on disk. Figure 7-1 shows in-memory and disk-resident trees before a merge.

图 7-1。刷新之前的两部分 LSM 树。刷新内存和磁盘驻留段以灰色显示。

刷新子树后，被取代的内存驻留子树和磁盘驻留子树将被丢弃并替换为它们的合并结果，该结果可从磁盘驻留树的预先存在的部分进行寻址。图 7-2显示了合并过程的结果，已写入磁盘上的新位置并附加到树的其余部分。

After the subtree is flushed, superseded memory-resident and disk-resident subtrees are discarded and replaced with the result of their merge, which becomes addressable from the preexisting sections of the disk-resident tree. Figure 7-2 shows the result of a merge process, already written to the new location on disk and attached to the rest of the tree.

图 7-2。刷新后的两部分 LSM 树。合并的内容以灰色显示。虚线框表示丢弃的磁盘段。

可以通过推进迭代器以锁步方式读取磁盘驻留叶节点和内存中树的内容来实现合并。由于两个源都已排序，为了生成排序的合并结果，我们只需要在合并过程的每个步骤中知道两个迭代器的当前值。

A merge can be implemented by advancing iterators reading the disk-resident leaf nodes and contents of the in-memory tree in lockstep. Since both sources are sorted, to produce a sorted merged result, we only need to know the current values of both iterators during each step of the merge process.

这种方法是我们关于不可变 B 树的对话的逻辑扩展和延续。写时复制B-Tree（参见“写时复制”）使用B-Tree结构，但它们的节点没有被完全占用，并且需要复制根叶路径上的页面并创建并行树结构。在这里，我们做了类似的事情，但是由于我们在内存中缓冲写入，因此我们分摊了磁盘驻留树更新的成本。

This approach is a logical extension and continuation of our conversation on immutable B-Trees. Copy-on-write B-Trees (see “Copy-on-Write”) use B-Tree structure, but their nodes are not fully occupied, and they require copying pages on the root-leaf path and creating a parallel tree structure. Here, we do something similar, but since we buffer writes in memory, we amortize the costs of the disk-resident tree update.

在实现子树合并和刷新时，我们必须确保三件事：

When implementing subtree merges and flushes, we have to make sure of three things:

1. 一旦刷新过程开始，所有新的写入都必须写入新的内存表。

2. As soon as the flush process starts, all new writes have to go to the new memtable.

3. 在子树刷新期间，磁盘驻留子树和刷新内存驻留子树都必须保持可访问以供读取。

4. During the subtree flush, both the disk-resident and flushing memory-resident subtree have to remain accessible for reads.

5. 刷新后，必须以原子方式执行发布合并的内容以及丢弃未合并的磁盘和内存驻留内容。

6. After the flush, publishing merged contents, and discarding unmerged disk- and memory-resident contents have to be performed atomically.

尽管两部分 LSM 树对于维护索引文件很有用，但截至撰写本文时，作者还不知道任何实现。这可以通过这种方法的写入放大特征来解释：合并相对频繁，因为它们是由内存表刷新触发的。

Even though two-component LSM Trees can be useful for maintaining index files, no implementations are known to the author as of time of writing. This can be explained by the write amplification characteristics of this approach: merges are relatively frequent, as they are triggered by memtable flushes.

多组件 LSM 树

Multicomponent LSM Trees

让我们考虑一下另一种设计是多组件 LSM 树，它不仅仅有一个磁盘驻留表。在这种情况下，整个内存表内容将在一次运行中刷新。

Let’s consider an alternative design, multicomponent LSM Trees that have more than just one disk-resident table. In this case, entire memtable contents are flushed in a single run.

很快就会发现，在多次刷新之后，我们最终会得到多个磁盘驻留表，并且它们的数量只会随着时间的推移而增长。由于我们并不总是确切地知道哪些表保存了所需的数据记录，因此我们可能必须访问多个文件才能找到搜索到的数据。

It quickly becomes evident that after multiple flushes we’ll end up with multiple disk-resident tables, and their number will only grow over time. Since we do not always know exactly which tables are holding required data records, we might have to access multiple files to locate the searched data.

必须从多个来源而不是仅从一个来源进行读取可能会变得昂贵。为了缓解这个问题并将表的数量保持在最低限度，称为定期合并过程 压缩（参见“LSM 树的维护”）被触发。压缩选择几个表，读取它们的内容，合并它们，并将合并结果写入新的组合文件。旧表在新合并表出现的同时被丢弃。

Having to read from multiple sources instead of just one might get expensive. To mitigate this problem and keep the number of tables to minimum, a periodic merge process called compaction (see “Maintenance in LSM Trees”) is triggered. Compaction picks several tables, reads their contents, merges them, and writes the merged result out to the new combined file. Old tables are discarded simultaneously with the appearance of the new merged table.

图 7-3显示了多组件 LSM Tree 数据生命周期。数据首先缓冲在内存驻留组件中。当它变得太大时，其内容将刷新到磁盘上以创建磁盘驻留表。随后，多个表被合并在一起以创建更大的表。

Figure 7-3 shows the multicomponent LSM Tree data life cycle. Data is first buffered in a memory-resident component. When it gets too large, its contents are flushed on disk to create disk-resident tables. Later, multiple tables are merged together to create larger tables.

图 7-3。多组件 LSM Tree 数据生命周期

本章的其余部分专门讨论多组件 LSM 树、构建块及其维护过程。

The rest of this chapter is dedicated to multicomponent LSM Trees, building blocks, and their maintenance processes.

内存表

In-memory tables

内存表刷新可以定期触发，或者通过使用大小阈值来触发。在刷新之前，必须切换内存表：分配一个新的内存表，它成为所有新写入的目标，而旧的则进入刷新状态。这两个步骤必须以原子方式执行。刷新内存表仍然可供读取，直到其内容完全刷新。此后，旧的内存表将被丢弃，取而代之的是新写入的磁盘驻留表，该表可供读取。

Memtable flushes can be triggered periodically, or by using a size threshold. Before it can be flushed, the memtable has to be switched: a new memtable is allocated, and it becomes a target for all new writes, while the old one moves to the flushing state. These two steps have to be performed atomically. The flushing memtable remains available for reads until its contents are fully flushed. After this, the old memtable is discarded in favor of a newly written disk-resident table, which becomes available for reads.

在图 7-4中，您可以看到 LSM Tree 的组件、它们之间的关系以及实现它们之间转换的操作：

In Figure 7-4, you see the components of the LSM Tree, relationships between them, and operations that fulfill transitions between them:

当前内存表

Current memtable

接收写入并提供读取服务。

Receives writes and serves reads.

刷新内存表

Flushing memtable

可供阅读。

Available for reads.

磁盘刷新目标

On-disk flush target

不参与读取，因为其内容不完整。

Does not participate in reads, as its contents are incomplete.

冲洗桌子

Flushed tables

一旦刷新的内存表被丢弃，就可以读取。

Available for reads as soon as the flushed memtable is discarded.

压实台

Compacting tables

当前正在合并磁盘驻留表。

Currently merging disk-resident tables.

压缩表

Compacted tables

从刷新或其他压缩表创建。

Created from flushed or other compacted tables.

图 7-4。LSM组件结构

数据已经在内存中排序，因此可以通过将内存驻留内容顺序写入磁盘来创建磁盘驻留表。在刷新期间，刷新内存表和当前内存表都可供读取。

Data is already sorted in memory, so a disk-resident table can be created by sequentially writing out memory-resident contents to disk. During a flush, both the flushing memtable and the current memtable are available for read.

在内存表完全刷新之前，其内容的唯一驻留在磁盘的版本将存储在预写日志中。当memtable内容完全刷新到磁盘上时，日志可以修剪，并且可以丢弃应用于刷新的内存表的保存操作的日志部分。

Until the memtable is fully flushed, the only disk-resident version of its contents is stored in the write-ahead log. When memtable contents are fully flushed on disk, the log can be trimmed, and the log section, holding operations applied to the flushed memtable, can be discarded.

更新和删除

Updates and Deletes

在LSM Trees、插入、更新和删除操作不需要在磁盘上定位数据记录。相反，冗余记录会在读取期间进行协调。

In LSM Trees, insert, update, and delete operations do not require locating data records on disk. Instead, redundant records are reconciled during the read.

从内存表中删除数据记录是不够的，因为其他磁盘或内存驻留表可能保存相同键的数据记录。如果我们仅通过从内存表中删除项目来实现删除，那么最终的删除要么没有影响，要么会恢复以前的值。

Removing data records from the memtable is not enough, since other disk or memory resident tables may hold data records for the same key. If we were to implement deletes by just removing items from the memtable, we would end up with deletes that either have no impact or would resurrect the previous values.

让我们考虑一个例子。刷新的磁盘驻留表包含v1与某个键关联的数据记录k1，并且内存表保存其新值v2：

Let’s consider an example. The flushed disk-resident table contains data record v1 associated with a key k1, and the memtable holds its new value v2:

磁盘表内存表
| k1 | v1 | | k1 | v2 |

Disk Table        Memtable
| k1 | v1 |       | k1 | v2 |

如果我们只是v2从内存表中删除并刷新它，我们就可以有效地复活v1，因为它成为与该键关联的唯一值：

If we just remove v2 from the memtable and flush it, we effectively resurrect v1, since it becomes the only value associated with that key:

磁盘表内存表
| k1 | v1 | ∅

Disk Table        Memtable
| k1 | v1 |       ∅

因为其中，删除需要明确记录。这可以通过插入特殊的删除条目（有时称为逻辑删除或休眠证书）来完成，指示删除与特定密钥关联的数据记录：

Because of that, deletes need to be recorded explicitly. This can be done by inserting a special delete entry (sometimes called a tombstone or a dormant certificate), indicating removal of the data record associated with a specific key:

磁盘表内存表
| k1 | v1 | | k1 | <墓碑> |

Disk Table        Memtable
| k1 | v1 |       | k1 | <tombstone> |

协调过程会拾取逻辑删除，并过滤掉隐藏的值。

The reconciliation process picks up tombstones, and filters out the shadowed values.

有时，删除连续范围的键而不是单个键可能会很有用。这可以做到使用谓词删除，其工作原理是在删除条目上附加一个根据常规记录排序规则进行排序的谓词。在协调期间，与谓词匹配的数据记录将被跳过并且不会返回给客户端。

Sometimes it might be useful to remove a consecutive range of keys rather than just a single key. This can be done using predicate deletes, which work by appending a delete entry with a predicate that sorts according to regular record-sorting rules. During reconciliation, data records matching the predicate are skipped and not returned to the client.

谓词可以采用 的形式DELETE FROM table WHERE key ≥ "k2" AND key < "k4"并且可以接收任何范围匹配器。阿帕奇卡桑德拉实现这种方法并调用它的墓碑不等。范围墓碑涵盖一系列键，而不仅仅是一个键。

Predicates can take a form of DELETE FROM table WHERE key ≥ "k2" AND key < "k4" and can receive any range matchers. Apache Cassandra implements this approach and calls it range tombstones. A range tombstone covers a range of keys rather than just a single key.

使用范围逻辑删除时，由于范围重叠和驻留在磁盘上的表边界，必须仔细考虑解析规则。例如，以下组合将隐藏与最终结果关联的数据k2记录k3：

When using range tombstones, resolution rules have to be carefully considered because of overlapping ranges and disk-resident table boundaries. For example, the following combination will hide data records associated with k2 and k3 from the final result:

磁盘表 1 磁盘表 2
| k1 | v1 | | k2| <start_tombstone_inclusive> |
| k2| v2 | | k4 | k4 | <end_tombstone_exclusive> |
| k3 | v3 |
| k4 | k4 | v4 |

Disk Table 1      Disk Table 2
| k1 | v1 |       | k2 | <start_tombstone_inclusive> |
| k2 | v2 |       | k4 | <end_tombstone_exclusive>   |
| k3 | v3 |
| k4 | v4 |

LSM 树查找

LSM Tree Lookups

LSM树由多个组件组成。在查找过程中，通常会访问多个组件，因此必须合并并协调它们的内容，然后才能将其返回给客户端。为了更好地理解合并过程，让我们看看合并过程中表是如何迭代的以及冲突的记录是如何合并的。

LSM Trees consist of multiple components. During lookups, more than one component is usually accessed, so their contents have to be merged and reconciled before they can be returned to the client. To better understand the merge process, let’s see how tables are iterated during the merge and how conflicting records are combined.

合并迭代

Merge-Iteration

自从磁盘驻留表的内容已排序，我们可以使用多路合并排序算法。例如，我们有三个源：两个磁盘驻留表和一个内存表。通常，存储引擎提供光标或迭代器来浏览文件内容。该游标保存最后消耗的数据记录的偏移量，可以检查迭代是否完成，并可用于检索下一个数据记录。

Since contents of disk-resident tables are sorted, we can use a multiway merge-sort algorithm. For example, we have three sources: two disk-resident tables and one memtable. Usually, storage engines offer a cursor or an iterator to navigate through file contents. This cursor holds the offset of the last consumed data record, can be checked for whether or not iteration has finished, and can be used to retrieve the next data record.

多路归并排序使用优先级队列，例如min-heap [SEDGEWICK11]，它可以容纳N元素（其中N是迭代器的数量），它对其内容进行排序并准备要返回的下一个最小元素。每个迭代器的头部被放入队列中。队列头部的元素是所有迭代器中的最小值。

A multiway merge-sort uses a priority queue, such as min-heap [SEDGEWICK11], that holds up to N elements (where N is the number of iterators), which sorts its contents and prepares the next-in-line smallest element to be returned. The head of each iterator is placed into the queue. An element in the head of the queue is then the minimum of all iterators.

当从队列中删除最小元素时，将检查与其关联的迭代器是否有下一个值，然后将其放入队列中，并重新排序以保留顺序。

When the smallest element is removed from the queue, the iterator associated with it is checked for the next value, which is then placed into the queue, which is re-sorted to preserve the order.

由于所有迭代器内容都已排序，因此从保存所有迭代器头的先前最小值的迭代器中重新插入值也会保留一个不变量，即队列仍然保存所有迭代器中的最小元素。每当其中一个迭代器耗尽时，算法就会继续进行，而不会重新插入下一个迭代器头。该算法将继续下去，直到满足查询条件或用尽所有迭代器。

Since all iterator contents are sorted, reinserting a value from the iterator that held the previous smallest value of all iterator heads also preserves an invariant that the queue still holds the smallest elements from all iterators. Whenever one of the iterators is exhausted, the algorithm proceeds without reinserting the next iterator head. The algorithm continues until either query conditions are satisfied or all iterators are exhausted.

图 7-5显示了刚刚描述的合并过程的示意图：头元素（源表中的浅灰色项）被放置到优先级队列中。优先级队列中的元素将返回到输出迭代器。结果输出已排序。

Figure 7-5 shows a schematic representation of the merge process just described: head elements (light gray items in source tables) are placed to the priority queue. Elements from the priority queue are returned to the output iterator. The resulting output is sorted.

在合并迭代过程中，我们可能会遇到同一键的多个数据记录。从优先级队列和迭代器不变量中，我们知道，如果每个迭代器每个键只保存一条数据记录，并且最终队列中同一键有多个记录，那么这些数据记录一定来自不同的迭代器。

It may happen that we encounter more than one data record for the same key during merge-iteration. From the priority queue and iterator invariants, we know that if each iterator only holds a single data record per key, and we end up with multiple records for the same key in the queue, these data records must have come from the different iterators.

图 7-5。LSM 合并机制

让我们一步一步地看一个例子。作为输入数据，我们在两个磁盘驻留表上有迭代器：

Let’s follow through one example step-by-step. As input data, we have iterators over two disk-resident tables:

迭代器 1： 迭代器 2：
{k2: v1} {k4: v2} {k1: v3} {k2: v4} {k3: v5}

Iterator 1:         Iterator 2:
{k2: v1} {k4: v2}   {k1: v3} {k2: v4} {k3: v5}

优先级队列从迭代器头开始填充：

The priority queue is filled from the iterator heads:

迭代器 1： 迭代器 2： 优先级队列：
{k4：v2} {k2：v4} {k3：v5} {k1：v3} {k2：v1}

Iterator 1:         Iterator 2:         Priority queue:
{k4: v2}            {k2: v4} {k3: v5}   {k1: v3} {k2: v1}

Keyk1是队列中最小的键，并附加到结果中。由于它来自Iterator 2，我们从中重新填充队列：

Key k1 is the smallest key in the queue and is appended to the result. Since it came from Iterator 2, we refill the queue from it:

迭代器 1: 迭代器 2: 优先级队列: 合并结果:
{k4：v2} {k3：v5} {k2：v1} {k2：v4} {k1：v3}

Iterator 1:         Iterator 2:         Priority queue:      Merged Result:
{k4: v2}            {k3: v5}            {k2: v1} {k2: v4}    {k1: v3}

现在，队列中的键有两条记录。k2由于上述不变量，我们可以确定任何迭代器中都不存在具有相同键的其他记录。相同键记录被合并并附加到合并结果中。

Now, we have two records for the k2 key in the queue. We can be sure there are no other records with the same key in any iterator because of the aforementioned invariants. Same-key records are merged and appended to the merged result.

队列重新填充来自两个迭代器的数据：

The queue is refilled with data from both iterators:

迭代器 1: 迭代器 2: 优先级队列: 合并结果:
{} {} {k3: v5} {k4: v2} {k1: v3} {k2: v4}

Iterator 1:         Iterator 2:         Priority queue:      Merged Result:
{}                  {}                  {k3: v5} {k4: v2}    {k1: v3} {k2: v4}

由于所有迭代器现在都是空的，我们将剩余的队列内容附加到输出中：

Since all iterators are now empty, we append the remaining queue contents to the output:

合并结果：
  {k1：v3} {k2：v4} {k3：v5} {k4：v2}

Merged Result:
  {k1: v3} {k2: v4} {k3: v5} {k4: v2}

总之，必须重复以下步骤来创建组合迭代器：

In summary, the following steps have to be repeated to create a combined iterator:

1. 最初，用每个迭代器的第一个项目填充队列。

2. Initially, fill the queue with the first items from each iterator.

3. 从队列中取出最小的元素（头）。

4. Take the smallest element (head) from the queue.

5. 从相应的迭代器重新填充队列，除非该迭代器已耗尽。

6. Refill the queue from the corresponding iterator, unless this iterator is exhausted.

就复杂性而言，合并迭代器与合并排序集合相同。它有O(N)内存开销，其中N是迭代器的数量。迭代器头的排序集合由O(log N)（平均情况）[KNUTH98]维护。

In terms of complexity, merging iterators is the same as merging sorted collections. It has O(N) memory overhead, where N is the number of iterators. A sorted collection of iterator heads is maintained with O(log N) (average case) [KNUTH98].

和解

Reconciliation

合并迭代这只是合并多个来源的数据所需执行的操作的一个方面。另一个重要方面是与同一密钥关联的数据记录的协调和冲突解决。

Merge-iteration is just a single aspect of what has to be done to merge data from multiple sources. Another important aspect is reconciliation and conflict resolution of the data records associated with the same key.

不同的表可能保存相同键的数据记录，例如更新和删除，并且它们的内容必须协调。前面示例中的优先级队列实现必须能够允许与同一键关联的多个值并触发协调。

Different tables might hold data records for the same key, such as updates and deletes, and their contents have to be reconciled. The priority queue implementation from the preceding example must be able to allow multiple values associated with the same key and trigger reconciliation.

为了协调数据记录，我们需要了解其中哪一项优先。数据记录保存为此所需的元数据，例如时间戳。为了建立来自多个来源的项目之间的顺序并找出哪一个较新，我们可以比较它们的时间戳。

To reconcile data records, we need to understand which one of them takes precedence. Data records hold metadata necessary for this, such as timestamps. To establish the order between the items coming from multiple sources and find out which one is more recent, we can compare their timestamps.

具有较高时间戳的记录所遮蔽的记录不会返回给客户端或在压缩期间写入。

Records shadowed by the records with higher timestamps are not returned to the client or written during compaction.

LSM 树的维护

Maintenance in LSM Trees

相似的对于可变 B 树，LSM 树需要维护。这些过程的性质很大程度上受到这些算法所保留的不变量的影响。

Similar to mutable B-Trees, LSM Trees require maintenance. The nature of these processes is heavily influenced by the invariants these algorithms preserve.

在 B 树中，维护过程收集未引用的单元格并对页面进行碎片整理，回收已删除和隐藏记录所占用的空间。在LSM Trees中，磁盘驻留表的数量不断增长，但可以通过触发定期压缩来减少。

In B-Trees, the maintenance process collects unreferenced cells and defragments the pages, reclaiming the space occupied by removed and shadowed records. In LSM Trees, the number of disk-resident tables is constantly growing, but can be reduced by triggering periodic compaction.

压缩选择多个磁盘驻留表，使用上述合并和协调算法迭代其整个内容，并将结果写入新创建的表中。

Compaction picks multiple disk-resident tables, iterates over their entire contents using the aforementioned merge and reconciliation algorithms, and writes out the results into the newly created table.

由于磁盘驻留表内容已排序，并且由于合并排序的工作方式，压缩具有理论上的内存使用上限，因为它应该仅将迭代器头保存在内存中。所有表内容都按顺序消费，并且生成的合并数据也按顺序写出。由于额外的优化，这些细节可能因实现而异。

Since disk-resident table contents are sorted, and because of the way merge-sort works, compaction has a theoretical memory usage upper bound, since it should only hold iterator heads in memory. All table contents are consumed sequentially, and the resulting merged data is also written out sequentially. These details may vary between implementations due to additional optimizations.

压缩表在压缩过程完成之前一直可供读取，这意味着在压缩期间，磁盘上需要有足够的可用空间来写入压缩表。

Compacting tables remain available for reads until the compaction process finishes, which means that for the duration of compaction, it is required to have enough free space available on disk for a compacted table to be written.

在任何给定时间，系统中都可以执行多次压缩。然而，这些并发压缩通常适用于不相交的表集。压缩编写器既可以将多个表合并为一个表，也可以将一个表分区为多个表。

At any given time, multiple compactions can be executed in the system. However, these concurrent compactions usually work on nonintersecting sets of tables. A compaction writer can both merge several tables into one and partition one table into multiple tables.

平整压实

Leveled compaction

压实为优化提供了多种机会，并且有许多不同的压缩策略。经常实施的压缩策略之一称为分层压缩。例如， RocksDB使用它。

Compaction opens up multiple opportunities for optimizations, and there are many different compaction strategies. One of the frequently implemented compaction strategies is called leveled compaction. For example, it is used by RocksDB.

分级压缩将磁盘驻留表分成多个级别。每个级别的表都有目标大小，每个级别都有相应的索引号（标识符）。有点违反直觉的是，指数最高的级别称为最底层。为了清楚起见，本节避免使用术语“更高级别”和“更低级别”，并使用相同的限定词来表示级别索引。也就是说，由于 2 大于 1，因此级别 2 的索引高于级别 1。术语“上一个”和“下一个”与级别索引具有相同的顺序语义。

Leveled compaction separates disk-resident tables into levels. Tables on each level have target sizes, and each level has a corresponding index number (identifier). Somewhat counterintuitively, the level with the highest index is called the bottommost level. For clarity, this section avoids using terms higher and lower level and uses the same qualifiers for level index. That is, since 2 is larger than 1, level 2 has a higher index than level 1. The terms previous and next have the same order semantics as level indexes.

0 级表是通过刷新内存表内容来创建的。0 级表可能包含重叠的键范围。一旦级别 0 上的表数量达到阈值，它们的内容就会合并，为级别 1 创建新表。

Level-0 tables are created by flushing memtable contents. Tables in level 0 may contain overlapping key ranges. As soon as the number of tables on level 0 reaches a threshold, their contents are merged, creating new tables for level 1.

1 级表和具有较高索引的所有级别的表的键范围不重叠，因此 0 级表必须在压缩过程中进行分区，拆分为范围，并与包含相应键范围的表合并。或者，压缩可以包括所有0 级和 1 级表，并输出分区的 1 级表。

Key ranges for the tables on level 1 and all levels with a higher index do not overlap, so level-0 tables have to be partitioned during compaction, split into ranges, and merged with tables holding corresponding key ranges. Alternatively, compaction can include all level-0 and level-1 tables, and output partitioned level-1 tables.

对具有较高索引的级别进行压缩会从具有重叠范围的两个连续级别中选取表，并在较高级别上生成一个新表。图7-6示意性地显示了压缩过程如何在级别之间迁移数据。压缩 1 级和 2 级表的过程将在 2 级上生成一个新表。根据表的分区方式，可以选择来自一个级别的多个表进行压缩。

Compactions on the levels with the higher indexes pick tables from two consecutive levels with overlapping ranges and produce a new table on a higher level. Figure 7-6 schematically shows how the compaction process migrates data between the levels. The process of compacting level-1 and level-2 tables will produce a new table on level 2. Depending on how tables are partitioned, multiple tables from one level can be picked for compaction.

图 7-6。压实过程。带虚线的灰色框表示当前正在压缩的表。级别范围的框表示级别上的目标数据大小限制。1 级已超出限制。

在不同的表中保留不同的键范围可以减少读取期间访问的表的数量。这是通过检查表元数据并过滤掉范围不包含搜索键的表来完成的。

Keeping different key ranges in the distinct tables reduces the number of tables accessed during the read. This is done by inspecting the table metadata and filtering out the tables whose ranges do not contain a searched key.

每个级别都有表大小和最大表数量的限制。一旦第 1 级或任何具有更高索引的级别上的表数量达到阈值，当前级别中的表就会与持有重叠键范围的下一个级别上的表合并。

Each level has a limit on the table size and the maximum number of tables. As soon as the number of tables on level 1 or any level with a higher index reaches a threshold, tables from the current level are merged with tables on the next level holding the overlapping key range.

级别之间的大小呈指数级增长：每个下一级上的表都比上一级上的表呈指数级增长。这样，最新的数据始终处于索引最低的级别，而较旧的数据逐渐迁移到索引较高的级别。

Sizes grow exponentially between the levels: tables on each next level are exponentially larger than tables on the previous one. This way, the freshest data is always on the level with the lowest index, and older data gradually migrates to the higher ones.

朗姆猜想

RUM Conjecture

一流行的存储结构成本模型考虑了三个因素：读取、更新和内存开销。它被称为 RUM 猜想[ATHANASSOULIS16]。

One of the popular cost models for storage structures takes three factors into consideration: Read, Update, and Memory overheads. It is called RUM Conjecture [ATHANASSOULIS16].

RUM 猜想指出，减少其中两项开销不可避免地会导致第三项开销变得更糟，并且只能以牺牲三个参数之一为代价来完成优化。我们可以根据这三个参数来比较不同的存储引擎，以了解它们针对哪些参数进行优化，以及这可能意味着哪些潜在的权衡。

RUM Conjecture states that reducing two of these overheads inevitably leads to change for the worse in the third one, and that optimizations can be done only at the expense of one of the three parameters. We can compare different storage engines in terms of these three parameters to understand which ones they optimize for, and which potential trade-offs this may imply.

理想的解决方案将提供最低的读取成本，同时保持较低的内存和写入开销，但实际上，这是无法实现的，我们需要进行权衡。

An ideal solution would provide the lowest read cost while maintaining low memory and write overheads, but in reality, this is not achievable, and we are presented with a trade-off.

B 树是读取优化的。写入 B 树需要在磁盘上定位记录，并且后续写入同一页面可能需要多次更新磁盘上的页面。为将来的更新和删除保留额外空间会增加空间开销。

B-Trees are read-optimized. Writes to the B-Tree require locating a record on disk, and subsequent writes to the same page might have to update the page on disk multiple times. Reserved extra space for future updates and deletes increases space overhead.

LSM Tree 不需要在写入期间在磁盘上定位记录，并且不为将来的写入保留额外的空间。存储冗余记录仍然会产生一些空间开销。在默认配置中，读取成本更高，因为必须访问多个表才能返回完整结果。然而，我们在本章中讨论的优化有助于缓解这个问题。

LSM Trees do not require locating the record on disk during write and do not reserve extra space for future writes. There is still some space overhead resulting from storing redundant records. In a default configuration, reads are more expensive, since multiple tables have to be accessed to return complete results. However, optimizations we discuss in this chapter help to mitigate this problem.

正如我们在有关 B 树的章节中以及在本章中看到的那样，有一些方法可以通过应用不同的优化来改进这些特性。

As we’ve seen in the chapters about B-Trees, and will see in this chapter, there are ways to improve these characteristics by applying different optimizations.

这种成本模型并不完美，因为它没有考虑其他重要指标，例如延迟、访问模式、实现复杂性、维护开销和硬件相关细节。对于分布式数据库很重要的更高级别的概念，例如一致性影响和复制开销，也没有被考虑。但是，该模型可以用作第一近似值和经验法则，因为它有助于理解存储引擎必须提供的功能。

This cost model is not perfect, as it does not take into account other important metrics such as latency, access patterns, implementation complexity, maintenance overhead, and hardware-related specifics. Higher-level concepts important for distributed databases, such as consistency implications and replication overhead, are also not considered. However, this model can be used as a first approximation and a rule of thumb as it helps understand what the storage engine has to offer.

排序字符串表

Sorted String Tables

到目前为止，我们已经讨论了 LSM 树的层次结构和逻辑结构（它们由多个驻留在内存和磁盘的组件组成），但尚未讨论如何实现磁盘驻留表以及它们的设计如何与其他组件一起使用系统的。

So far we’ve discussed the hierarchical and logical structure of LSM Trees (that they consist of multiple memory- and disk-resident components), but have not yet discussed how disk-resident tables are implemented and how their design plays together with the rest of the system.

磁盘驻留表通常使用排序字符串表（SSTables）来实现。顾名思义，SSTable 中的数据记录按键顺序排序和布局。SSTables通常由两个部分组成：索引文件和数据文件。索引文件是使用某种允许对数查找（例如 B 树）或恒定时间查找（例如哈希表）的结构来实现的。

Disk-resident tables are often implemented using Sorted String Tables (SSTables). As the name suggests, data records in SSTables are sorted and laid out in key order. SSTables usually consist of two components: index files and data files. Index files are implemented using some structure allowing logarithmic lookups, such as B-Trees, or constant-time lookups, such as hashtables.

由于数据文件按键顺序保存记录，因此使用哈希表进行索引并不妨碍我们实现范围扫描，因为哈希表仅用于定位范围中的第一个键，并且范围本身可以从数据文件中顺序读取，而范围谓词仍然匹配。

Since data files hold records in key order, using hashtables for indexing does not prevent us from implementing range scans, as a hashtable is only accessed to locate the first key in the range, and the range itself can be read from the data file sequentially while the range predicate still matches.

索引组件保存键和数据条目（实际数据记录所在的数据文件中的偏移量）。数据组件由串联的键值对组成。我们在第 3 章中讨论的单元格设计和数据记录格式很大程度上适用于 SSTable。这里的主要区别在于，单元格是按顺序写入的，并且在 SSTable 的生命周期内不会被修改。由于索引文件保存指向数据文件中存储的数据记录的指针，因此在创建索引时必须知道它们的偏移量。

The index component holds keys and data entries (offsets in the data file where the actual data records are located). The data component consists of concatenated key-value pairs. The cell design and data record formats we discussed in Chapter 3 are largely applicable to SSTables. The main difference here is that cells are written sequentially and are not modified during the life cycle of the SSTable. Since the index files hold pointers to the data records stored in the data file, their offsets have to be known by the time the index is created.

在压缩期间，可以顺序读取数据文件而无需寻址索引组件，因为其中的数据记录已经排序。由于压缩期间合并的表具有相同的顺序，并且合并迭代是保留顺序的，因此生成的合并表也是通过在单次运行中顺序写入数据记录来创建的。一旦文件被完全写入，它就被认为是不可变的，并且其驻留在磁盘上的内容不会被修改。

During compaction, data files can be read sequentially without addressing the index component, as data records in them are already ordered. Since tables merged during compaction have the same order, and merge-iteration is order-preserving, the resulting merged table is also created by writing data records sequentially in a single run. As soon as the file is fully written, it is considered immutable, and its disk-resident contents are not modified.

布隆过滤器

Bloom Filters

这LSM 树中读放大的根源在于我们必须寻址多个磁盘驻留表才能完成读操作。发生这种情况是因为我们并不总是预先知道磁盘驻留表是否包含所搜索键的数据记录。

The source of read amplification in LSM Trees is that we have to address multiple disk-resident tables for the read operation to complete. This happens because we do not always know up front whether or not a disk-resident table contains a data record for the searched key.

防止表查找的方法之一是将其键范围（给定表中存储的最小和最大键）存储在元数据中，并检查搜索的键是否属于该表的范围。该信息并不精确，只能告诉我们该数据记录是否可以存在于表中。为了改善这种情况，包括Apache Cassandra和RocksDB在内的许多实现都使用称为Bloom filter 的数据结构。

One of the ways to prevent table lookup is to store its key range (smallest and largest keys stored in the given table) in metadata, and check if the searched key belongs to the range of that table. This information is imprecise and can only tell us if the data record can be present in the table. To improve this situation, many implementations, including Apache Cassandra and RocksDB, use a data structure called a Bloom filter.

布隆过滤器由 Burton Howard Bloom 在 1970 年提出[BLOOM70]，是一种节省空间的概率数据结构，可用于测试元素是否是集合的成员。它可以产生误报匹配（假设该元素是集合的成员，但它不存在于集合中），但不能产生漏报匹配（如果返回否定匹配，则保证该元素不是集合的成员）集）。

A Bloom filter, conceived by Burton Howard Bloom in 1970 [BLOOM70], is a space-efficient probabilistic data structure that can be used to test whether the element is a member of the set or not. It can produce false-positive matches (say that the element is a member of the set, while it is not present there), but cannot produce false negatives (if a negative match is returned, the element is guaranteed not to be a member of the set).

换句话说，布隆过滤器可以用来判断键是否可能在表中或者绝对不在表中。查询期间将跳过布隆过滤器返回负匹配的文件。访问其余文件以查明数据记录是否确实存在。使用与磁盘驻留表关联的布隆过滤器有助于显着减少读取期间访问的表的数量。

In other words, a Bloom filter can be used to tell if the key might be in the table or is definitely not in the table. Files for which a Bloom filter returns a negative match are skipped during the query. The rest of the files are accessed to find out if the data record is actually present. Using Bloom filters associated with disk-resident tables helps to significantly reduce the number of tables accessed during a read.

布隆过滤器使用大型位数组和多个哈希函数。哈希函数应用于表中记录的键，以查找位数组中的索引，其位设置为1。由散列函数确定的所有位置中设置的位1指示密钥在集合中的存在。在查找过程中，当检查布隆过滤器中是否存在元素时，会再次计算该键的哈希函数，如果所有哈希函数确定的位均为1，则返回肯定结果，表明该项目以一定的概率是该集合的成员。如果至少有一位是0，我们可以准确地说该元素不存在于集合中。

A Bloom filter uses a large bit array and multiple hash functions. Hash functions are applied to keys of the records in the table to find indices in the bit array, bits for which are set to 1. Bits set to 1 in all positions determined by the hash functions indicate a presence of the key in the set. During lookup, when checking for element presence in a Bloom filter, hash functions are calculated for the key again and, if bits determined by all hash functions are 1, we return the positive result stating that item is a member of the set with a certain probability. If at least one of the bits is 0, we can precisely say that element is not present in the set.

哈希值应用于不同键的函数可以返回相同的位位置并导致哈希冲突，并且1位仅意味着某个哈希函数已经为某个键生成了该位位置。

Hash functions applied to different keys can return the same bit position and result in a hash collision, and 1 bits only imply that some hash function has yielded this bit position for some key.

误报的概率是通过配置位集的大小和哈希函数的数量来管理的：位集越大，冲突的可能性越小；类似地，拥有更多的哈希函数，我们可以检查更多的位并得到更精确的结果。

Probability of false positives is managed by configuring the size of the bit set and the number of hash functions: in a larger bit set, there’s a smaller chance of collision; similarly, having more hash functions, we can check more bits and have a more precise outcome.

较大的位集占用更多的内存，更多的哈希函数的计算结果可能会对性能产生负面影响，因此我们必须在可接受的概率和产生的开销之间找到合理的中间立场。概率可以根据预期的集合大小来计算。由于 LSM 树中的表是不可变的，因此集合大小（表中键的数量）是预先已知的。

The larger bit set occupies more memory, and computing results of more hash functions may have a negative performance impact, so we have to find a reasonable middle ground between acceptable probability and incurred overhead. Probability can be calculated from the expected set size. Since tables in LSM Trees are immutable, set size (number of keys in the table) is known up front.

我们来看一个简单的例子，如图7-7所示。我们有一个 16 路位数组和 3 个哈希函数，它们产生值3、5和。我们现在在这些位置设置位。添加下一个键，散列函数产生、和for的值，我们也为其设置位。10key15814key2

Let’s take a look at a simple example, shown in Figure 7-7. We have a 16-way bit array and 3 hash functions, which yield values 3, 5, and 10 for key1. We now set bits at these positions. The next key is added and hash functions yield values of 5, 8, and 14 for key2, for which we set bits, too.

图 7-7。布隆过滤器

key3现在，我们尝试检查集合中是否存在，并且哈希函数产生3、10和14。key1由于在添加和时设置了所有三个位key2，因此布隆过滤器返回误报的情况：key3从未附加到那里，但所有计算的位都已设置。然而，由于布隆过滤器仅声明该元素可能在表中，因此该结果是可以接受的。

Now, we’re trying to check whether or not key3 is present in the set, and hash functions yield 3, 10, and 14. Since all three bits were set when adding key1 and key2, we have a situation in which the Bloom filter returns a false positive: key3 was never appended there, yet all of the calculated bits are set. However, since the Bloom filter only claims that element might be in the table, this result is acceptable.

如果我们尝试查找并接收、和key4的值，我们会发现只有一位被设置，而其他两位未被设置。如果其中一位未设置，我们就可以确定该元素从未被附加到过滤器中。59155

If we try to perform a lookup for key4 and receive values of 5, 9, and 15, we find that only bit 5 is set, and the other two bits are unset. If even one of the bits is unset, we know for sure that the element was never appended to the filter.

跳表

Skiplist

那里有许多不同的数据结构用于在内存中保存排序数据，其中一种由于其简单性而最近变得越来越流行，称为跳跃列表[ PUGH90b]。在实现方面，跳跃列表并不比单链表复杂多少，并且其概率复杂性保证接近于搜索树。

There are many different data structures for keeping sorted data in memory, and one that has been getting more popular recently because of its simplicity is called a skiplist [PUGH90b]. Implementation-wise, a skiplist is not much more complex than a singly-linked list, and its probabilistic complexity guarantees are close to those of search trees.

Skiplists 不需要旋转或重新定位插入和更新，而是使用概率平衡。与内存中的 B 树相比，跳表通常不太适合缓存，因为跳表节点很小并且在内存中随机分配。一些实现通过使用展开的链接列表来改善这种情况。

Skiplists do not require rotation or relocation for inserts and updates, and use probabilistic balancing instead. Skiplists are generally less cache-friendly than in-memory B-Trees, since skiplist nodes are small and randomly allocated in memory. Some implementations improve the situation by using unrolled linked lists.

跳跃列表由一系列不同高度的节点组成，构建链接的层次结构，允许跳过项目范围。每个节点都拥有一个密钥，并且与链表中的节点不同，某些节点具有多个后继者。高度为 的节点由一个或多个高度不超过h的前驱节点链接。最低层的节点可以从任意高度的节点链接。 h

A skiplist consists of a series of nodes of a different height, building linked hierarchies allowing to skip ranges of items. Each node holds a key, and, unlike the nodes in a linked list, some nodes have more than just one successor. A node of height h is linked from one or more predecessor nodes of a height up to h. Nodes on the lowest level can be linked from nodes of any height.

节点高度由随机函数确定，并在插入期间计算。具有相同高度的节点形成一个级别。层数受到限制以避免无限增长，并且最大高度是根据结构可以容纳的物品数量来选择的。每个下一级的节点数量呈指数级减少。

Node height is determined by a random function and is computed during insert. Nodes that have the same height form a level. The number of levels is capped to avoid infinite growth, and a maximum height is chosen based on how many items can be held by the structure. There are exponentially fewer nodes on each next level.

查找通过跟踪最高层的节点指针来进行。一旦搜索遇到拥有比搜索到的键更大的键的节点，就会遵循其前任到下一级节点的链接。换句话说，如果搜索到的关键字大于当前节点关键字，则继续向前搜索。如果搜索到的关键字小于当前节点关键字，则从下一级的前驱节点继续搜索。递归地重复此过程，直到找到所搜索的关键字或其前身。

Lookups work by following the node pointers on the highest level. As soon as the search encounters the node that holds a key that is greater than the searched one, its predecessor’s link to the node on the next level is followed. In other words, if the searched key is greater than the current node key, the search continues forward. If the searched key is smaller than the current node key, the search continues from the predecessor node on the next level. This process is repeated recursively until the searched key or its predecessor is located.

例如，在图7-8所示的跳跃列表中搜索键7可以如下完成：

For example, searching for key 7 in the skiplist shown in Figure 7-8 can be done as follows:

1. 沿着最高层的指针，到达保存 key 的节点10。

2. Follow the pointer on the highest level, to the node that holds key 10.

3. 由于搜索到的 key7小于，因此 10从头节点开始的下一级指针将定位到持有 key 的节点5。

4. Since the searched key 7 is smaller than 10, the next-level pointer from the head node is followed, locating a node holding key 5.

5. 跟踪该节点上的最高层指针，10再次定位持有密钥的节点。

6. The highest-level pointer on this node is followed, locating the node holding key 10 again.

7. 查找到的关键字7小于，则从保存关键字的节点开始的下一级指针，定位到保存 查找到的关键字 的节点。1057

8. The searched key 7 is smaller than 10, and the next-level pointer from the node holding key 5 is followed, locating a node holding the searched key 7.

图 7-8。跳表

在插入过程中，使用上述算法找到插入点（持有键或其前驱的节点），并创建一个新节点。为了构建树状层次结构并保持平衡，节点的高度是使用根据概率分布生成的随机数来确定的。前任节点中持有比新创建节点中的键更小的键的指针被链接以指向该节点。他们的高层指针保持不变。新创建的节点中的指针链接到每个级别上相应的后继节点。

During insert, an insertion point (node holding a key or its predecessor) is found using the aforementioned algorithm, and a new node is created. To build a tree-like hierarchy and keep balance, the height of the node is determined using a random number, generated based on a probability distribution. Pointers in predecessor nodes holding keys smaller than the key in a newly created node are linked to point to that node. Their higher-level pointers remain intact. Pointers in the newly created node are linked to corresponding successors on each level.

在删除过程中，被删除节点的前向指针被放置到相应级别的前驱节点。

During delete, forward pointers of the removed node are placed to predecessor nodes on corresponding levels.

我们可以通过实现线性化方案来创建跳跃列表的并发版本，该方案使用一个附加fully_linked标志来确定节点指针是否完全更新。可以使用比较和交换[HERLIHY10]设置此标志。这是必需的，因为必须在多个级别上更新节点指针才能完全恢复跳表结构。

We can create a concurrent version of a skiplist by implementing a linearizability scheme that uses an additional fully_linked flag that determines whether or not the node pointers are fully updated. This flag can be set using compare-and-swap [HERLIHY10]. This is required because the node pointers have to be updated on multiple levels to fully restore the skiplist structure.

在具有非托管内存模型的语言、引用计数或危险指针可用于确保当前引用的节点在并发访问时不会被释放[RUSSEL12]。该算法是无死锁的，因为节点总是从更高级别访问。

In languages with an unmanaged memory model, reference counting or hazard pointers can be used to ensure that currently referenced nodes are not freed while they are accessed concurrently [RUSSEL12]. This algorithm is deadlock-free, since nodes are always accessed from higher levels.

Apache Cassandra 使用跳表来实现二级索引 memtable。WiredTiger 使用跳表进行一些内存操作。

Apache Cassandra uses skiplists for the secondary index memtable implementation. WiredTiger uses skiplists for some in-memory operations.

磁盘访问

Disk Access

由于大多数表内容都驻留在磁盘上，并且存储设备通常允许按块访问数据，因此许多 LSM Tree 实现依赖于页面缓存来进行磁盘访问和中间缓存。《缓冲区管理》中描述的许多技术，例如页面驱逐和固定，仍然适用于日志结构存储。

Since most of the table contents are disk-resident, and storage devices generally allow accessing data blockwise, many LSM Tree implementations rely on the page cache for disk accesses and intermediate caching. Many techniques described in “Buffer Management”, such as page eviction and pinning, still apply to log-structured storage.

最显着的区别是内存中的内容是不可变的，因此不需要额外的锁或闩锁来进行并发访问。应用引用计数来确保当前访问的页面不会从内存中逐出，并且在压缩期间删除底层文件之前，正在进行的请求完成。

The most notable difference is that in-memory contents are immutable and therefore require no additional locks or latches for concurrent access. Reference counting is applied to make sure that currently accessed pages are not evicted from memory, and in-flight requests complete before underlying files are removed during compaction.

另一个区别是LSM Tree中的数据记录不一定是页对齐的，并且指针可以使用绝对偏移量而不是页ID来实现寻址。在图7-9中，您可以看到内容与磁盘块不对齐的记录。有些记录跨越页面边界，需要在内存中加载多个页面。

Another difference is that data records in LSM Trees are not necessarily page aligned, and pointers can be implemented using absolute offsets rather than page IDs for addressing. In Figure 7-9, you can see records with contents that are not aligned with disk blocks. Some records cross the page boundaries and require loading several pages in memory.

图 7-9。未对齐的数据记录

压缩

Compression

我们已经已经在 B 树上下文中讨论了压缩（参见“压缩”）。类似的想法也适用于 LSM 树。这里的主要区别是 LSM Tree 表是不可变的，并且通常是在单遍中编写的。当按页压缩数据时，压缩页不是页对齐的，因为它们的大小小于未压缩页的大小。

We’ve discussed compression already in context of B-Trees (see “Compression”). Similar ideas are also applicable to LSM Trees. The main difference here is that LSM Tree tables are immutable, and are generally written in a single pass. When compressing data page-wise, compressed pages are not page aligned, as their sizes are smaller than that of uncompressed ones.

为了能够寻址压缩页面，我们需要在写入内容时跟踪地址边界。我们可以用零填充压缩页面，将它们与页面大小对齐，但这样我们就会失去压缩的好处。

To be able to address compressed pages, we need to keep track of the address boundaries when writing their contents. We could fill compressed pages with zeros, aligning them to the page size, but then we’d lose the benefits of compression.

为了使压缩页面可寻址，我们需要一个间接层来存储压缩页面的偏移量和大小。图 7-10显示了压缩块和未压缩块之间的映射。压缩后的页面总是比原始页面小，否则压缩它们是没有意义的。

To make compressed pages addressable, we need an indirection layer which stores offsets and sizes of compressed pages. Figure 7-10 shows the mapping between compressed and uncompressed blocks. Compressed pages are always smaller than the originals, since otherwise there’s no point in compressing them.

图 7-10。读取压缩块。虚线表示从映射表到磁盘上压缩页偏移量的指针。未压缩的页面通常驻留在页面缓存中。

在compaction和flush过程中，压缩页被顺序追加，压缩信息（原始未压缩页偏移量和实际压缩页偏移量）存储在单独的文件段中。在读取过程中，会查找压缩页偏移量及其大小，并且可以将该页解压缩并在内存中具体化。

During compaction and flush, compressed pages are appended sequentially, and compression information (the original uncompressed page offset and the actual compressed page offset) is stored in a separate file segment. During the read, the compressed page offset and its size are looked up, and the page can be uncompressed and materialized in memory.

比特桶

Bitcask

比特桶，一个Riak中使用的存储引擎是一个无序日志结构存储引擎[SHEEHY10b]。与到目前为止讨论的日志结构存储实现不同，它不使用内存表进行缓冲，而是将数据记录直接存储在日志文件中。

Bitcask, one of the storage engines used in Riak, is an unordered log-structured storage engine [SHEEHY10b]. Unlike the log-structured storage implementations discussed so far, it does not use memtables for buffering, and stores data records directly in logfiles.

为了使值可搜索，Bitcask 使用称为keydir的数据结构，它保存对相应键的最新数据记录的引用。旧的数据记录可能仍然存在于磁盘上，但不会从 keydir 引用，并且会在压缩期间被垃圾收集。Keydir 被实现为内存中的哈希图，并且必须在启动期间从日志文件重建。

To make values searchable, Bitcask uses a data structure called keydir, which holds references to the latest data records for the corresponding keys. Old data records may still be present on disk, but are not referenced from keydir, and are garbage-collected during compaction. Keydir is implemented as an in-memory hashmap and has to be rebuilt from the logfiles during startup.

在写入过程中，密钥和数据记录会依次追加到日志文件中，并且指向新写入的数据记录位置的指针会放置在 keydir 中。

During a write, a key and a data record are appended to the logfile sequentially, and the pointer to the newly written data record location is placed in keydir.

读取检查 keydir 以找到搜索到的键，并跟随关联的日志文件指针，找到数据记录。由于在任何给定时刻，keydir 中只能有一个与键关联的值，因此点查询不必合并来自多个源的数据。

Reads check the keydir to locate the searched key and follow the associated pointer to the logfile, locating the data record. Since at any given moment there can be only one value associated with the key in the keydir, point queries do not have to merge data from multiple sources.

Bitcask中数据文件中的键和记录的映射关系如图7-11所示。日志文件保存数据记录，keydir 指向与每个键关联的最新实时数据记录。数据文件中的隐藏记录（被后来的写入或删除取代的记录）显示为灰色。

Figure 7-11 shows mapping between the keys and records in data files in Bitcask. Logfiles hold data records, and keydir points to the latest live data record associated with each key. Shadowed records in data files (ones that were superseded by later writes or deletes) are shown in gray.

图 7-11。Bitcask 中 keydir 和数据文件之间的映射。实线表示从键到与其关联的最新值的指针。阴影键/值对以浅灰色显示。

在压缩过程中，所有日志文件的内容都会按顺序读取、合并并写入到新位置，仅保留实时数据记录并丢弃隐藏的数据记录。Keydir 已更新为指向重新定位的数据记录的新指针。

During compaction, contents of all logfiles are read sequentially, merged, and written to a new location, preserving only live data records and discarding the shadowed ones. Keydir is updated with new pointers to relocated data records.

数据记录直接存储在日志文件中，因此不必维护单独的预写日志，这减少了空间开销和写入放大。这种方法的缺点是它只提供点查询并且不允许范围扫描，因为项目在 keydir 和数据文件中都是无序的。

Data records are stored directly in logfiles, so a separate write-ahead log doesn’t have to be maintained, which reduces both space overhead and write amplification. A downside of this approach is that it offers only point queries and doesn’t allow range scans, since items are unordered both in keydir and in data files.

这种方法的优点是简单和出色的点查询性能。即使存在多个版本的数据记录，keydir 也只能寻址最新的版本。然而，必须将所有密钥保留在内存中并在启动时重建 keydir 是一些限制，对于某些用例来说可能会破坏交易。虽然这种方法非常适合点查询，但它不提供对范围查询的任何支持。

Advantages of this approach are simplicity and great point query performance. Even though multiple versions of data records exist, only the latest one is addressed by keydir. However, having to keep all keys in memory and rebuilding keydir on startup are limitations that might be a deal breaker for some use cases. While this approach is great for point queries, it does not offer any support for range queries.

威斯凯

WiscKey

范围查询对于许多应用程序都很重要，如果有一个存储结构能够具有无序存储的写入和空间优势，同时仍然允许我们执行范围扫描，那就太好了。

Range queries are important for many applications, and it would be great to have a storage structure that could have the write and space advantages of unordered storage, while still allowing us to perform range scans.